LeetCode 84.柱状图中最大的矩形

Source

今天还是分享一道才刷过的题目, 柱状图中最大的矩形,这道题根上一篇我分享的接雨水类似,都是可以用双指针,动态规划(双指针加备忘录),单调栈来算

这道题的话三种方法都写了,双指针会超时,优化一下备忘录是可以的。不过这篇还是分享一下用单调栈的做法。毕竟上一道题我没写这种方法哈哈哈

单调栈一般解决的问题都是类似的,找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,用空间去换时间的一种思路,栈里一般放的是元素下标

比方说找比当前元素第一个大的元素,我们就可以构建一个单调递减的栈,栈里元素从栈底到栈顶是依次减小的,如果遇到个元素比栈顶元素大,那么就说明这个栈顶元素找到了比自己大的第一个数字..一般就是一个for去遍历,里面套一个while,while来操作栈

有关单调栈的一些简单介绍可以看看甜姐的视频,我贴在这里了

刷题论|单调栈真没你想的那么难

这篇重点还是在将这道题,用单调栈的思路来说

这道题和接雨水一点不同,接雨水那个是找每个柱子左右两边最高的,只有找到最高的才能构成凹,里面才能接上水 

而这道题呢根据力扣上面的图示我再形象一下

就是这么个图,我们比方说此时在i这个位置的柱子,找他能构成矩形的最大面积,肯定就是往右往左走,看图就能看出来,i往右边画不了了,因此挨着的都比他小,往左边可以画,直到画到要小于他的那个位置。

因此我们就能懂了,这道题要找柱子两边第一个比他矮的位置,找到之后两个位置的区间就是构成矩形的长

从示例就能看出,找到右边第一个比他矮的下标为right,左边第一个比他矮的下标为left,那么这个柱子能构成最大矩形的长为(right-left-1)

这篇文章我刚开始也说了,如果找第一个最大的元素,那么去维护一个递减的单调栈

那这个题既然要找第一个小的,我们如果去维护一个递增的单调栈,就是去找第一个最小元素解释一下:如果数组元素 2 3 5 4 1,栈里面比如此时是2 3 5 ,此时我们遍历到数组元素是4,如果4入栈的话就会破坏栈的单调性,因为4比此时栈顶小,那么栈顶出栈,说明此时栈顶元素5找到了第一个比他小的元素,就是4,记录一下。5出栈了之后,3就成了新栈顶,4比3大,那么4继续入栈,现在遍历1,1比4小,4出栈说明,1是4最近的比他小的元素;4出栈,栈里剩了2 3,然后循环继,1比较发现,1比3也小,如果1入栈的话又破坏单调性了,所以3出栈,1也是3最近的一个比他小的元素....一次下去,记住一般入栈入的都是数组下标,stack记录的是下标!!我们根据下标去修改对应位置元素

大概就是这种基本思路,单调栈一类的题

 注意:

  1. 栈入的是下标,但是是按元素来比,到时候根据下标来记录对应元素所需要的值
  2. 给数组加两个哨兵结点,遇到边界调节,比如最左边元素的矩形,他没有左边了,right-left-1就会有问题,右边同理,怕他一直是单调递增的,没法正常计算

  3. 这样操作的话while里面求w=right-left-1的时候,边界就不用做特殊判断了

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int>sk;
        int res=0;
        //加两个哨兵结点,遇到边界调节比如最左边元素的矩形,他没有左边了,right-left-1就会有问题
        //这样操作的话while里面求w=right-left-1的时候,边界就不用做特殊判断了
        heights.insert(heights.begin(),0);
        heights.emplace_back(0);

        sk.push(0);//把第一个元素下标加进去,其实就是上面新增的左哨兵,

        for(int i=1;i<heights.size();++i)
        {
            //heights[i] < heights[stk.top()]就是我们要计算以stk.top()这个柱子为矩形高度的矩形的时候了
           
            while(heights[i]<heights[sk.top()])//第一个比他小
            {
                //我直接按照对应的元素来解释了,虽然入的是下标
                int index=sk.top();//sk里面是 2 3 5  此时5是top,遍历height[i]是4,
                                     //说明5找到了右边比他小的了
                                                  
                sk.pop();    //5出栈  剩了2 3  因为构成了单调递增栈
                int left=sk.top();   //3就是 5左边第一个比他小的,算一下他对应位置
                int right=i;   //右边第一个比他矮的位置
                int w=right-left-1; //算一下此时5的最大矩形长
                int h=heights[index];//5的高度
                res=max(res,w*h);  //5 最大矩形的面积
            }
            sk.push(i);
        }
        return res;

    }
};

好嘞好嘞,今日记录就到这,跟上一节接雨水放在一起咯