单调栈

理解：栈内元素的大小按照它们在栈内的位置，满足一定的单调性。这种数据结构通常运用在一维数组上。如果遇到问题与前后元素之间的大小关系有联系的话(如leetcode 84/85/42)，我们可以试图用单调栈来解决。使用单调栈，关键在于每个元素出栈的意义。由于每个元素都出栈入栈一次，时间复杂度O(n)。

例1：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;++i)
        cin>>v[i];
    // 维护一个单调递增栈
    stack<int>s;
    // 对每个位置 要求输出的索引对
    map<int,pair<int,int>>mp;
    for(int i=0;i<n;++i)
    {
           // 当前元素小于栈顶元素，那么栈顶元素要求的左右两个位置已经得到
           while(!s.empty()&&v[i]<v[s.top()])
            {
                int cur = s.top();
                s.pop();
                int left = s.empty() ? -1:s.top();
                mp[cur] = make_pair(left,i);
            }
            s.push(i);
    }
    // 结算阶段 （所有元素右侧均没有比它自己小的元素）
    while(!s.empty())
    {
        int cur = s.top();
        s.pop();
        int left = s.empty() ?  -1:s.top();
        mp[cur] = make_pair(left,-1);

    }
    for(auto it = mp.begin();it!=mp.end();it++)
    {
        cout<<it->second.first<<" "<<it->second.second<<endl;
    }
    return 0;
}

例2.接雨水

思路：每个位置的盛水量取决于min(该位置左边高度最大值，该位置右边高度最大值)-这个位置本身的高度。
法一：求解出每个位置左右两边最大高度值并记录下来。接下来累加每个位置的接水量即可。O(n)。
法二：单调栈法。维护一个单调递减栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定；如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加到结果中。O(n)。

class Solution {
public:
    int trap(vector<int>& height) {
        // 单调递减栈法
        stack<int>s;
        int ans = 0;
        for(int i=0;i<height.size();++i)
        {
            // 形成一个能盛水的容器
            while(!s.empty()&&height[i]>height[s.top()])
            {
                int cur = s.top();
                s.pop();
                if(s.empty()) break;
                // 容器两侧相隔的距离
                int distance = i - s.top()-1;
                {
                    // 盛水量取决于较短的边，且要减去当前位置占据的空间
                    ans += (min(height[i],height[s.top()]) - height[cur])*distance;
                }
            }
            s.push(i);
        }
        return ans;

    }
};