力扣Hot100——柱状图中最大矩形（单调栈）

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked

经典的单调栈问题
思路：考虑单调递增栈，如果说我拿到的数字比栈顶来的要小，那么说明了我前面比我高的会被我自身的高度限制，所以前面的矩阵要依次出栈统计出来这个局部的最高高度，然后把目前的高度+前面比我高的宽度压入栈中。这题拿数组去模拟栈效果更加好。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] stack = new int[heights.length+10];
        int[] weight = new int[stack.length];
        int p = 0;
        int ans = 0;        
        for(int i=0;i<heights.length;i++){
            //如果比我当前高
            if(stack[p]<=heights[i]){
                stack[++p] = heights[i];
                weight[p] = 1; 
            }
            else{
                int w = 0;
                while(p>0&&stack[p]>heights[i]){
                    w +=weight[p];
                    int h = stack[p];
                    p--;
                    ans = Math.max(ans,h*w);
                }
                //最后再将这个数压入栈中，宽度应该是出栈统计出来的宽+自身的1
                stack[++p] = heights[i];
                weight[p] = w+1;
            }
        }
        //最后递增，栈中还有数，全部拉出来统计一轮
        int w = 0;
        while(p>0){
            w +=weight[p];
            int h = stack[p];
            p--;
            ans = Math.max(ans,h*w);
        }
        return ans;
    }
}
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