Leetcode 84_柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

想法：感觉这个题考的是数学，是逻辑。

怎么找矩形呢？就是当前位置的最高点，向左和向右画矩形，找他比他矮的点 left,right，就停止。

高度就是 height<i>

宽度就是(right-left+1)-2，因为找到的那两个点是不能算进去的，所以要-2，理解这个-2，后面的优化算法也就好理解了。

一、暴力枚举

我在暴力枚举的时候，向左向右找的点，是&gt;=自己高度的最后一个点，所以是 right-left+1。

    public int largestRectangleArea2(int[] heights) {
        int n = heights.length;
        int max = 0;
        int last = -1;
        for (int i = 0; i < n; i++) {
            int h = heights[i];
            // 剪枝操作，这一步让测试通过了
            if (h == last) {
                continue;
            }
            int left = -1;
            int right = -1;
            // to right
            for (int j = i + 1; j < n; j++) {
                if (heights[j] < h) { right = j - 1; break; } } if (right == -1) { right = n - 1; } for (int j = i - 1; j >= 0; j--) {
                if (heights[j] < h) {
                    left = j + 1;
                    break;
                }
            }
            if (left == -1) {
                left = 0;
            }
            max = Math.max((right - left + 1) * h, max);
            last = h;
        }
        return max;
    }

二、优化算法

难点就在于怎么找两边的那两个点。因为每个点都是不同高度的，我的思维就限在了，怎么去区分不同的高度上。实际上不用关心具体的高度，只用关心高度是上升还是下降的。记住拐点。

哨兵+栈

一头一尾插入哨兵

过程中怎么找矩形呢？

• 遍历开始
  • 把“我” 和 栈顶元素比，一旦我比栈顶元素 a 矮，那栈顶元素的矩形面积就到头了（因为它不能再延伸了），则进入循环
  • pop 栈顶元素 a
  • 其面积由它向两边延伸的第一个矮点确定，两边第一个矮点分别是我和下一个栈顶元素
  • 宽度 = ( 我 – 下一个栈顶元素 b + 1 ) – 2
  • 循环直到我>=栈顶元素可跳出循环
• push 我
• 遍历结束

1、ArrayDeque 存储

    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int n = heights.length + 2;
        int[] newHeights = new int[n];
        System.arraycopy(heights, 0, newHeights, 1, n - 2);
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for (int i = 1; i < n; i++) {
            int h = heights[i];
            while (h < heights[stack.peek()]) { // 发现了拐点（确定了两个矮点），进入循环
                int confirmIdx = stack.pop(); // 该位置最大矩形已确认
                max = Math.max(max, heights[confirmIdx] * (i - stack.peek() - 1)); // 即两个矮点的距离-2
            }
            stack.push(i);
        }
        return max;
    }

2、int[]手搓一个栈

    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int n = heights.length + 2;
        int[] newHeights = new int[n];
        System.arraycopy(heights, 0, newHeights, 1, n - 2);
        heights = newHeights;

        int[] stack = new int[heights.length];
        int top = 0;
        stack[0] = 0;
        for (int i = 1; i < n; i++) {
            int h = heights[i];
            while (h < heights[stack[top]]) {
                int confirmIdx = stack[top--];
                max = Math.max(max, heights[confirmIdx] * (i - stack[top] - 1));
            }
            stack[++top] = i;
        }
        return max;
    }

以上关于Leetcode 84_柱状图中最大的矩形的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。