柱状图中最大的矩形

84. 柱状图中最大的矩形

难度困难1350收藏分享切换为英文接收动态反馈

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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

暴力遍历（超时）

class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int n = heights.length;

        for(int i=0;i<n;i++){
            int w = 0;
            int h = heights[i];
            for(int j=i;j >= 0 && heights[j] >= h;j--){
                w++;
            }
            for(int j = i+1; j < n && heights[j] >= h; j++){
                w++;
            }
            max = Math.max(max,h * w);
        }
        return max;
    }
}

单调栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;

        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length); 

        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;

        for(int i = 0; i < tmp.length; i++){
            while(!stack.isEmpty() && tmp[i] < tmp[stack.peek()]){
                int hIndex = stack.pop();
                max = Math.max(tmp[hIndex] * (stack.isEmpty() ? i : (i - stack.peek() - 1)), max);   
            }
            stack.push(i);
        }
        return max;
    }
}

赏

谢谢你请我吃糖果

微信