单调栈

Monotonic stack

Definition

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。
单调栈被分为单调递增栈和单调递减栈：
* 单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大 * 单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小 ## Establishing process 比如建立一个单调递减栈，对于每一个即将入栈的元素：
* 检查栈是否为空，如果为空，则直接入栈 * 如果不为空，检查栈顶元素是否大于（等于）即将入栈元素，如果是，则入栈 * 如果不是，将栈顶元素出栈，然后重复整个整个过程。
## Application
* 例1：

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

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;
    }
};

• 例二：
  
  答案：

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;
    }
};