问题链接

84. 柱状图中最大的矩形

问题描述

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

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

示例

解题思路

1. 暴力解法：枚举以每个柱形为高度的最大矩形的面积
依次遍历每个柱形；对于每个柱形，要以这个柱形的高度作为最高高度；同时，我们从这跟柱子开始向两侧延伸，直到遇到高度小于 最高高度 的柱子，就确定了矩形的左右边界。
注：这个解法会超时。

2.单调栈：以解法1的思路为基础，借助单调栈找左右边界
我们需要一个单调递增的栈，遍历柱形高度：
如果当前柱形高度比栈顶元素代表的柱形的高度大，将当前柱形丢到栈里；同时，刚刚的栈顶元素就是它的左边界；
如果当前柱形高度比栈顶元素代表的柱形的高度小，从栈里取出栈顶元素，直到当前柱形高度比栈顶元素大（或栈空了），将当前柱形丢入栈；和上一个步骤一样，这里找到了左边界；另外要注意的是：当前高度是抛出的栈顶元素的右边界；
处理完之后，如果栈里还有元素，他们的右边界是最右边。

代码示例（JAVA）

1. 暴力解法

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            // 当前柱形高度为0，跳过
            if (heights[i] == 0) {
                continue;
            }
            int x = i, y = i + 1;
            while (x - 1 >= 0 && heights[x - 1] >= heights[i]) {
                x--;
            }
            while ( y <= heights.length - 1 && heights[y] >= heights[i]) {
                y++;
            }
            int area = (y - x) * heights[i];
            maxArea = Math.max(area, maxArea);
        }
        return maxArea;
    }
}

时间复杂度：O(N²)
执行结果

2.单调栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        Arrays.fill(right, heights.length);

        Stack<Integer> stack = new Stack();
        // 找左边界， 同时找右边界
        for (int i = 0; i < heights.length; i++) {
            while (!stack.empty() && heights[stack.peek()] >= heights[i]) {
                right[stack.peek()] = i;
                stack.pop();
            }
            left[i] = stack.empty() ? -1 : stack.peek();
            stack.push(i);
        }
        // 栈里剩余的数，右边界就是最右边
        // 也可以在一开始，right数组全给height.length
        // while (!stack.empty()) {
        //     right[stack.peek()] = heights.length;
        //     stack.pop();
        // }
        
        // 找最大矩形
        int maxArea = Integer.MIN_VALUE;
        for (int i = 0; i < heights.length; i++) {
            int area = (right[i] - left[i] - 1) * heights[i];
            maxArea = Math.max(maxArea, area);
        }
        
        return maxArea;
    }
}

时间复杂度：O(N)
执行结果