您现在的位置是:首页 > 正文

单调栈-图解-LeetCode84柱状图中最大的矩形

2024-04-01 00:50:38阅读 2

概念:

单调栈(monotone-stack)是指栈内元素(栈底到栈顶)都是(严格)单调递增或者单调递减的。

如果有新的元素入栈,栈调整过程中 *会将所有破坏单调性的栈顶元素出栈,并且出栈的元素不会再次入栈* 。由于每个元素只有一次入栈和出栈的操作,所以 *单调栈的维护时间复杂度是O(n)* 。

单调栈性质:
1. 单调栈里的元素具有单调性。
2. 递增(减)栈中可以找到元素左右两侧比自身小(大)的第一个元素。

我们主要使用第二条性质,该性质主要体现在栈调整过程中,下面以递增栈为例(假设所有元素都是唯一),当新元素入栈。
+ 对于出栈元素来说:找到右侧第一个比自身小的元素。
+ 对于新元素来说:等待所有破坏递增顺序的元素出栈后,找到左侧第一个比自身小的元素。

 

leetcode 84实例:

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/ 

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

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

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

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

示例:

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

用单调栈解题:

 

  • 图解详细步骤:

        这里很巧妙的一点是:每次有元素出栈时计算面积(并与maxArea比较,更新最大值),pop出栈的元素是所求矩形的height对应的index(由此可获取到矩形的),pop之后的栈顶(peek)元素是该矩形的的左边界,当前for循环中的i所表示的index是的右边界,“右边界-左边界-1”即为该矩形的

       

        此图结合下图step4来看,index=2出栈的时候,计算该面积,此时height[2]=5-->高,栈中剩下[-1,1],(因为3在2之前已经出栈,4还未入栈),栈顶元素为1-->左边界,当前循环索引i=4--->右边界,则面积=(右边界-左边界-1)*高=(4-1-1)*5=10.

        这里把栈水平放置,方便对照原图横坐标来看。

 

单调栈代码(Java):

    // 单调栈!!!
    public int largestRectangleArea2(int[] heights) {
        int len = heights.length;
        if(len==0) return 0;
        if(len==1) return heights[0];
        int maxArea = 0;
        int[] newHeights = new int[len+2];
        System.arraycopy(heights,0,newHeights,1,len);
        Deque<Integer> stack = new ArrayDeque<>();
        len += 2;
        for (int i = 0; i < len; i++) {
            while(!stack.isEmpty()  && newHeights[i]<newHeights[stack.peek()]){
                int curHei = newHeights[stack.poll()];
                maxArea = Math.max(maxArea,(i-stack.peek()-1)*curHei);
            }
            stack.push(i);
        }
        return maxArea;
    }

附(暴力解法代码)(Java):

    // 暴力
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if(len<1) return 0;
        int maxArea = 0;
        for (int i = 0; i < len; i++) {
            int minHi = heights[i];
            // maxArea = Math.max(maxArea,heights[i]);
            for (int j = i+1; j < len; j++) {
                minHi = Math.min(minHi,heights[j]);
                maxArea = Math.max(maxArea,minHi*(j+1-i));
            }
        }
        return maxArea;
    }

小结:

单调栈的作用/什么时候用单调栈
        单调栈可以以 O(1) 的时间复杂度得知某个位置左右两侧比他大(或小)的数的位置,当你需要高效率获取某个位置左右两侧比他大(或小)的数的位置的的时候就可以用到单调栈。

        说人话,结合上题,就是当从左到右遍历的过程中(找右边界),又需要回头查找(即从右到左找左边界),这就像极了栈结构LIFO(后进先出/倒序输出),此时就需要利用单调栈

        我们在缓存数据的时候,是从左向右缓存的,我们计算出一个结果的顺序是从右向左的,并且计算完成以后我们就不再需要了,符合后进先出的特点。因此,我们需要的这个作为缓存的数据结构就是

        当确定了一个柱形的高度的时候,我们就将它从栈顶移出,所有的柱形在栈中进栈一次,出栈一次,一开始栈为空,最后也一定要让栈为空,表示这个高度数组里所有的元素都考虑完了。

求解数组中元素右边第一个比它的元素的下标,从前往后,构造单调递栈;
求解数组中元素右边第一个比它的元素的下标,从前往后,构造单调递栈;
求解数组中元素左边第一个比它的元素的下标,从后往前,构造单调递栈;
求解数组中元素左边第一个比它的元素的下标,从后往前,构造单调递栈。

 

以下列出了单调栈的问题,供大家参考

序号    题目                                        题解
1    42. 接雨水(困难)                    暴力解法、优化、双指针、单调栈
2    739. 每日温度(中等)               暴力解法 + 单调栈
3    496. 下一个更大元素 I(简单)  暴力解法、单调栈
4    316. 去除重复字母(困难)        栈 + 哨兵技巧(Java、C++、Python)
5    901. 股票价格跨度(中等)     「力扣」第 901 题:股票价格跨度(单调栈)
6    402. 移掉K位数字    
7    581. 最短无序连续子数组    

另有详细图解说明请参考leetcode大神:

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/

 

 

如有错误或不当之处,请批评指正!

 

网站文章