单调栈

Posted on Edited on

单调栈

从名字上就听的出来，单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈

  • 单调递增栈：(上面元素是最小元素) 单调递增栈就是从栈底到栈顶数据是从大到小
  • 单调递减栈：(上面元素是最大元素) 单调递减栈就是从栈底到栈顶数据是从小到大

应用题目1

​ 1.视野总和

描叙：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2

==转换：从后向前遍历，计算所有元素与上一个比它大的元素的间隔之和==

1
2
3



应用题目2

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

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

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

输出: 10

单调栈用法：

官方给出的题解是利用单调栈计算出每个点展开左右边界，保存在了left和right中 （我自己写时，也想到这个问题，不过没有采用合适的数据结构vector,而是采用栈–自己之所以采用栈是为了配合单调栈，但其实是每个结点都需要保存他的左右边界)

如何确定左右边界

单调栈中保存从左到右遍历 递增序列的index 每个结点的左边界为栈中相邻+靠栈低的元素（从左遍历，最近的且小于该处高度的点） 单调栈保存index

结点的右边界为 右侧第一个小于当前高度的索引，所以最开始入栈时，是不确定的

确定某个左右边界的时间：
  • 右边界 当结点从单调栈中弹出时，计算它的右边界。 按照单调栈的结构，当结点遇到第一个比它高度小的结点，该结点就会被弹出。这就是它的右边界，如果遍历完数组，仍在栈中，默认右边界为n
  • 左边界 当结点压入栈中时，计算它的左边界。 左边界为当前栈顶元素，如果栈为空则是-1 再把该节点的index压入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
          int n = heights.size();
    vector<int> left(n),right(n,n);//用于保存左右边界

    stack<int> index;///用于增序排列
    for(int i=0;i<heights.size();i++){
        while(! index.empty() && heights[i]<= heights[index.top()]){
            right[index.top()] = i;//右边界可以确定了
            index.pop();
        }
        left[i]= index.empty()?-1:index.top(); //它的左边界也可以确定了
        index.push(i);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        int temp =heights[i]*(right[i]-left[i]-1);
        if(ans<temp){
            ans = temp;
        }
    }
    return ans;
    }
};

​ 应用题目3

456. 132 模式

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/132-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.empty()){
            return false;
        }
        stack<int> item;
        item.push(nums[nums.size()-1]);
        int max_k = INT_MIN;
        for(int i=nums.size()-2;i>=0;i--){
            if(nums[i]<max_k){
                return true;
            }
            while(!item.empty() && item.top()<nums[i] ){
                max_k = item.top();
                item.pop();
            }
            item.push(nums[i]);
        }
        return false;
    }
};

递减栈(栈顶保存最小的元素）
回顾本题解决思路
寻找是否有132模式

从右到左进行遍历

我们希望确定3之后，2是3右侧小于3的最大的数，方便更好地判断 1是否存在。

  • 如何确定32结构

从右到左遍历
这里利用递减栈可以 保存当前值 距离 右侧第一个大于它的数 之间，最大的那个元素(保存在max_k中)
即维护递减栈过程中，更新当前pop的最大值

  • 何时确定？
    • 确定32结构:
      遍历栈时，如果有nums[i]>item.top()，更新max_k，保存最新的32结构
    • 要一开始就判断是否存在 1
      如果nums[i] <max_k ,则一定存在132模式