单调栈 Summary (Leetcode 456, Leetc

单调栈的用法是：用来找数组，左边或右边，第一个比当前元素小（或者大）的是谁。即insert前，栈顶的元素。一个递增的单调栈如下：
递减的也可以相应实现。

for(int i=0; i<nums.size(); i++){
     while(!st.empty() && st.top() >= nums[i]){
           st.pop();
     }
}

同时，一个重要的变形是单调栈可以用deque实现，来找比当前元素小的最小元素。

单调栈相对灵活，对元素的处理可以在pop的时候，或者在while loop以外，即push之前。一个基本的框架就是扫两次，第一次从左往右，第二次从右往左。第一次扫完，用map记录该index的结果。即key为index。

Leetcode 456

bool find132pattern(vector<int>& nums) {
    if(nums.size() < 3) return false;
    deque<int> dq;
    stack<int> st1;
    unordered_map<int, int> mp;
    for(int i=0; i<nums.size(); i++){
        while(!dq.empty() && dq.back() >= nums[i]){
            dq.pop_back();
        }
        if(!dq.empty()) mp[i] = dq.front();
        else mp[i] = INT_MAX;
        dq.push_back(nums[i]);
    }
    
    for(int i=nums.size()-1; i>=0; i--){
        while(!st1.empty() && st1.top() < nums[i]){
            if(st1.top() > mp[i]) return true;
            st1.pop();
        }
        st1.push(nums[i]);
    }
    return false;
}

这道题中，更加巧妙的做法如下(真是巧妙)，从后往前传递，先找到第二大的数( s2 > s3 > s1, 利用单调栈找s3)，然后判断前面是否有s1.

bool find132pattern(vector<int>& nums) {
        if(nums.size() < 3) return false;
        int s3 = INT_MIN;
        stack<int> st;
        for(int i=nums.size()-1; i>=0; i--){
            if(nums[i] < s3) return true;
            while(!st.empty() && st.top() < nums[i]){
                s3 = max(s3, st.top());
                st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }

Lintcode 122:

int largestRectangleArea(vector<int> &height) {
    // write your code here
    if(height.empty()) return 0;
    stack<int> st;
    unordered_map<int, int> mp;
    for(int i=0; i<height.size(); i++){
        while(!st.empty() && height[st.top()] >= height[i]){
            st.pop();
        }
        if(!st.empty()) mp[i] += height[i] * (i - st.top());
        else mp[i] += height[i] * (i+1);
        st.push(i);
    }
    stack<int> st2;
    for(int i=height.size()-1; i>=0; i--){
        while(!st2.empty() && height[st2.top()] >= height[i]){
            st2.pop();
        }
        if(!st2.empty()) mp[i] += height[i] * (st2.top() - 1 - i);
        else mp[i] += height[i] * (height.size() - 1 - i);
        st2.push(i);
    }
    int max_ret = 0;
    for(auto it : mp){
        max_ret = max(max_ret, it.second);
    }
    return max_ret;
    
}

122也有一遍扫的办法：

int largestRectangleArea(vector<int> &height) {
        // write your code here
        if(height.empty()) return 0;
        stack<int> st;
        unordered_map<int, int> mp;
        int max_area = 0;
        height.insert(height.begin(), -1);
        height.push_back(-1);
        for(int i=0; i<height.size(); i++){
            while(!st.empty() && height[st.top()] > height[i]){
                int cur_idx = st.top(); st.pop();
                int area = height[cur_idx] * (i - 1 - st.top());
                max_area = max(max_area, area);
            }
            st.push(i);
        }
        return max_area;
    }