单调栈相关习题

判别是否需要使用单调栈，如果需要找到左边或者右边第一个比当前位置的数大或者小，则可以考虑使用单调栈；单调栈的题目如矩形米面积等等

Leetcode42.接雨水

思路：从左到右遍历数组，维护一个单调递减的栈，看图很好理解，从左往右遍历时，当高度逐渐减少，此时不会产生水量，如果出现了一个比当前栈中最小的值高的情况：即：

此时我们就需要计算水量，而水量的计算需要几个值，即坑的宽度，瓶颈高度，坑的高度，

然后由瓶颈高度减去坑的高度乘以坑的宽度可得。

为什么 要用瓶颈高度减去坑的高度呢？

坑的高度是由当前栈中需要d出的值来决定的， （这个d出的值就是比当前遍历到的height[i]要小的值。）

于是代码如下：（注意要区分下标和高度）

对于栈，我们存放的是下标。为什么是存放下标而不是存放高度？因为计算宽度时需要有下标，如果存放的是高度则不知道下标，而且我们可以从下标知高度，反过来却不行

class Solution {
public:
    int trap(vector& height) {
        stack st;
        int sum=0;
        for(int i=0;iheight[st.top()]){
                int holeIndex=st.top();//坑的下标(命名为index而不是高度，高度需要另外表示)
                int holeHeight=height[holeIndex];

                st.pop();

                if(st.empty())break;
                //如果栈为空，说明这个坑左边没有高度
                int holeLeftIndex=st.top();
                int neckHeight=min(height[holeLeftIndex],height[i]);//在两者中最小的将作为瓶颈
                int holeWidth=i-holeLeftIndex-1;
                int water=holeWidth*neckHeight;
                cout<<"index:"<

Leetcode84.柱状图中最大的矩形

先来看看本题暴力法：

 

 

 

暴力解法的缺点是在每一个遍历时没有为下一个下标得到什么帮助。

优化思路是空间换时间。

观察下面这个图：

从左往右遍历时，我们以高度来看矩形，当遍历到下标1时，由于下标1的高度小于下标0的高度，则此时以0为高度的矩形，其面积就已经可以确定了。

同理，从1遍历到3时，高度不断增加，则此时前面的矩形，其宽度都可以不断延申。

 

但是当从3到4时，高度下降，那么此时高度为3的矩形，其面积就已经可以确定了。

而同理，前面以2号位的高作为的矩形，其面积也可以确定了。因为它比最新的5号位要高。

因此，先确定3号位矩形的面积，然后进而可以确定2号位矩形的面积，观察到这个规律符合先进后出，即符合栈的规律，因此此处可以使用栈，并且我们可以去维护这个单调栈。

因此思路如下：

可以维护一个单调递增的栈，当出现元素不递增时，此即为前面有高度大于当前高度，即面积可以确定了。那么此时将所有大于当前高度的栈元素依次出栈，并且在出栈时就可以计算出面积了。

（但是这样的思路并不齐全，还有许多特殊情况。）

 

以及

原因在于我只考虑到单调栈是递增的，没想到还有相等的情况。

 

 

还有这样的例子：

绿色即为最大面积

 此时当遍历到下标1时，前面下标0的元素已经出栈。

• 特殊情况1：

当遍历完成以后，将栈中剩下的元素出栈时：

此时矩形的宽度是可以延申到最末尾的！

此时

 

故此时宽度为len-1-st.top()

(此时的st.top是d出了当前元素后的，例如上图中当前遍历的元素为4，而前一个元素下标为1，即为此时的st.top())

对于上面这种情况，分析得出：当栈内的元素全部出栈时，此时栈顶的元素一定可以扩散到末尾。

• 特殊情况2：

 

 

每日温度

下一个更大元素

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/728236.html