doovvv
0%

单调栈

Posted on Edited on Valine:

Monotonic stack

Definition

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。
单调栈被分为单调递增栈和单调递减栈：

  • 单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大
  • 单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小

    Establishing process

    比如建立一个单调递减栈，对于每一个即将入栈的元素：
  • 检查栈是否为空，如果为空，则直接入栈
  • 如果不为空，检查栈顶元素是否大于（等于）即将入栈元素，如果是，则入栈
  • 如果不是，将栈顶元素出栈，然后重复整个整个过程。

    Application

  • 例1：

    本题寻找下一个更大元素的过程就可以使用单调递减栈结构。
    对于某个元素，当他出栈时，即将入栈的那个元素就是他的下一个更大元素。
    本体答案为： 

    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
    26
    27
    28
    29
    class Solution { 
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            map<int,int> ans;
            stack<int> s;
            nums2.push_back(INT_MAX); //to pop all entries
            for(int i = 0;i<nums2.size();i++){
                if(s.empty() || s.top()>=nums2[i]){
                    s.push(nums2[i]);
                }
                else{
                    while(!s.empty() && s.top()<nums2[i]){
                        ans[s.top()] = nums2[i];
                        s.pop();
                    }
                    s.push(nums2[i]);
                }
            }
            cout<<ans[2];
            vector<int> re_ans(nums1.size(),-1);
            for(int i = 0;i<nums1.size();i++){
                if(ans.find(nums1[i]) != ans.end()){
                    
                    re_ans[i] = ans[nums1[i]] == INT_MAX?-1: ans[nums1[i]];
                }
            }
            return re_ans;
        }
    };

  • 例二：

    答案：

    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
    26
    27
    28
    29
    30
    31
    class Solution {
    public:
        int trap(vector<int>& height) {
            if(height.size()<= 2){
                return 0;
            }
            int count = 0;
            stack<int> s;
            for(int i = 0;i<height.size();i++){
                if(s.empty()){
                    s.push(i);
                    continue;
                }
                else if(height[i] < height[s.top()]){
                    s.push(i);
                    continue;
                }
                while(!s.empty() && height[i]>= height[s.top()]){
                    int j = s.top();
                    s.pop();
                    if(s.empty()){
                        break;
                    }
                    int k =s.top();
                    count += (min(height[k],height[i])-height[j])*(i-k-1);
                }
                s.push(i);   
            }
            return count;
        }
    };