力扣Hot100——柱状图中最大矩形(单调栈)

2023-12-28 14:42:22

题目链接: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;
    }
}

文章来源:https://blog.csdn.net/qq_45816864/article/details/135267843
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。