單調(diào)棧的用法是：用來找數(shù)組，左邊或右邊，第一個比當(dāng)前元素?。ɑ蛘叽螅┑氖钦l。即insert前，棧頂?shù)脑?。一個遞增的單調(diào)棧如下：
遞減的也可以相應(yīng)實現(xiàn)。

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

同時，一個重要的變形是單調(diào)?？梢杂胐eque實現(xiàn)，來找比當(dāng)前元素小的最小元素。

單調(diào)棧相對靈活，對元素的處理可以在pop的時候，或者在while loop以外，即push之前。一個基本的框架就是掃兩次，第一次從左往右，第二次從右往左。第一次掃完，用map記錄該index的結(jié)果。即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;
}

這道題中，更加巧妙的做法如下(真是巧妙)，從后往前傳遞，先找到第二大的數(shù)( s2 > s3 > s1, 利用單調(diào)棧找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;
    }