单调栈的理解和学习

## 单调栈
### (1)定义：
`单调栈`，顾名思义，是栈内元素保持一定单调性（单调递增或单调递减）的栈。这里的单调递增或递减是指的从栈底到栈顶单调递增或递减。既然是栈，就满足`后进先出`的特点，与之相对应的是单调队列。
（可以参考：https://blog.csdn.net/weixin_43283687/article/details/85164863，不过这个博客的单调性与我们这里的相反，不过无所谓，叫法不同而已）。
###（2）可以解决的问题
很多博客都提到了这个问题，包括上面的这个博客链接，但很多都不是很好理解。下面给我的个人理解：单调栈主要用来求解所有满足一定单调性的所有子区间。
比如：
`对于单调递增栈，可以用来求解所有的凸型子区间（如leetcode 84题，907题）；
单调递减栈可以求解所有的凹槽区间（如leetcode 42题 接雨水）`，
或者也可以说是：`利用单调栈，可以找到从左/右遍历第一个比它小/大的元素的位置`

比如，stk为单增栈，nums为输入序列，i为待入栈元素的索引，
此时，nums[i]已经不再大于stk.top()，那么，对于栈顶元素stk.top()来说，栈顶元素的前一个元素，到待入栈元素这个区间，就是待求区间！写成代码就是`int curr_index = stk.pop();stk.pop(); ans = f(stk.top(),curr_index,i)`,其中f理解为一个函数即可，根据具体的需求确定。比如leetcode的第84题f就为：`max_area = max(max_area,nums[curr_index]*(i - stk.top()-1));`

907题也是类似的解法。

### (3)参考代码：
（Leetcode 84题：求柱状图中最大的矩形面积）
```
/*
*
* 本代码对应的是单调递增栈，时间复杂度只有O(n) 
*共n个元素，编号为0~n-1
*/
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        //将输入序列的首尾均补上足够小的值；
        heights.push_back(0);
        heights.insert(heights.begin(),0);
        stack<int> stk;
        int max_area = 0; 
        for(int i =0;i<heights.size();i++)
        {
            while(!stk.empty() && heights[i]<heights[stk.top()])
            {
                int curr_index = stk.top();
                stk.pop();
                //这里为找到区间后，计算ans = f(stk.top(),curr_index,i)
                max_area = max(max_area,heights[curr_index]*(i - stk.top()-1));
            }
            stk.push(i);
        }
        return max_area;
        }
};

//907题几乎完全类似84题：
class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        const int mod = 1e9 + 7;
        A.push_back(0);
        A.insert(A.begin(), 0);
        const int n = A.size();
        //单调递增栈
        stack<int> stk;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && A[i]<A[stk.top()]) {
                int curr = stk.top(); 
                stk.pop();
                ans = (ans + ((i - curr) * (curr - stk.top()))* A[curr])%mod;
                /*
                核心思路就是：单调栈找每个元素左边右边第一个小于该元素的数的下标
                
                对于每个值，我们计算以它为最小值的[i,j]范围有多少个。比如：
                3 5 2 6
                以2为最小值的范围有3 * 2个。（可以这么算，左边3 5 2，5 2， 2有3个，右边2 6， 2有两个，组合）
                */
            }
            stk.push(i);
        }
        return ans%mod;
    }
};

```

Leetcode 42题：接雨水
```
class Solution {
public:
    int trap(vector<int>& height) {
         //单调栈,从栈底到栈顶递减
         stack<int> stk;
         int total_rain = 0;
         for(int i = 0;i<height.size();i++)
         {
            while(!stk.empty()&& height[i] > height[stk.top()])
            {
                int curr_index =stk.top();
                stk.pop();
                if(!stk.empty())
                {
                   total_rain+= (min(height[i],height[stk.top()]) - height[curr_index])*(i - stk.top()-1);
                }
            }
            stk.push(i);
         }
        return total_rain;
    }
};
```

lee-romantic 's Blog

导航

最近发表

友情链接