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;
    }