力扣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;iheights.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;
    }
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: PHP中GET和POST方法的区别是什么？

在 PHP 中，GET 和 POST 是用于从客服务器托管网户端向服务器传递数据的两种常用的 HTTP 请求方法。它们之间的主要区别在于数据传递的方式和使用场景。 GET 方法： 数据传递方式： 使用 URL 参数传递数据，数据附加在 URL 后面，以 ? 开…