lc84.柱状图中最大的矩形

发表于

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

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

1

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

1

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

示例:

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

又是看题解的一天，看了weiwei老师的解答视频

这一题用辅助栈解答，java中的stack因历史遗留问题，官方建议使用Deque来实现栈的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Sulution {
    private static int largestRectangleArea(int[] heights){
        int len=heights.length;
        if(len==0) return 0;
        if(len==1) return heights[0];
        int area=0;
        Deque<Integer> stack=new ArrayDeque<>();
        /*fori从头到尾遍历i，默认压栈
        while()重复比较栈顶与i的大小，栈顶比i大就弹栈removeLast()(前者在数组中左右数值都比它小，
                它本身最大矩形面积为自身)
        弹栈之后width为i-stack.peekLast()-1，因为是(peekLast(),i)的全开区间
        栈该弹出的元素弹出完毕，最后再把i压栈
        */
        for (int i = 0; i <len ; i++) {
            while(!stack.isEmpty()&&heights[stack.peekLast()]>heights[i]){
                int height=heights[stack.removeLast()];
                while(!stack.isEmpty()&&heights[stack.peekLast()]==height){
                    stack.removeLast();
                }
                int width;
                if (stack.isEmpty()){
                    width=i;
                } else {
                    width=i-stack.peekLast()-1;
                }
                area=Math.max(area,width*height);
            }
            stack.addLast(i);
        }
        //遍历完毕，开始弹栈，width=(peekLast(),len)的全开区间
        while(!stack.isEmpty()){
            int height=heights[stack.removeLast()];
            while(!stack.isEmpty()&&heights[stack.peekLast()]==height){
                stack.removeLast();
            }
            int width;
            if (stack.isEmpty()){
                width=len;
            } else {
                width=len-stack.peekLast()-1;
            }
            area=Math.max(area,width*height);
        }
        return area;
    }

    public static void main(String[] args) {
        int[] test={2,1,5,6,2,3};
        int[] test1={1,1};
        int ans=largestRectangleArea(test);
        System.out.println(ans);
    }
}