最近刷了不少单调栈，总算搞懂了
基本性质
- 入栈顺序为下标顺序。
- 出栈序列分批次为单调增/单调减。
- 每个元素应当入栈一次出栈一次，复杂度为O(N)
利用好这3点性质，是发挥单调栈作用的关键：
对于性质1，我们可以认为：当你使用了单调栈，那么你所解决的问题一定与数组下标顺序(或者排序后的数组下标顺序)有关系。相当于帮你固定了题目中的一组偏序。对于性质2，我们认为：想要使用单调栈，那么答案或者中间结果必然具有某种单调性。对于性质3，当我们需要O(N)算法时，可以考虑单调栈。
说的过于抽象了，看题。
类型1：分批次计算后方元素对前方元素影响
这是最经典且最简单的单调栈应用，看最经典的题：
下一个更大的元素1
给一个序列，要求找到序列中每个元素后面第一个比他大的元素。
在说单调栈正解之前，我们考虑用其他的方法解决这个问题：
所谓找下一个更大的元素，就是在【比a[i]大的所有元素中】找【数组下标大于i】的第一个元素。因此，我们按照这个思路，可以维护一个set(或平衡树)：我们先对数组排序，一开始set是全空的，然后把整个数组里最大的数字下标插进去，然后这个数字的答案是-1(没有比他更大的了)。然后，我们继续遍历数组，对于每个元素a[i]，在set中二分查找下标i，找到比它下标大的第一个元素，即为答案，然后再把a[i]插进去，开始处理下一个元素。
观察一下刚刚我们做的事情：排序，在set里二分，实际是先固定了元素本身大小的单调，然后再用set帮我们处理数组下标的顺序，这样本身是有点反人类思维的。而单调栈与这种做法相反，是固定了数组下标顺序，利用后方元素对前方元素的影响解题。
利用这个性质，我们很容易得到一个单调栈解法：维护一个栈，按顺序遍历数组，当a[i]要入栈时，检查栈顶，如果栈顶<a[i]，那么弹出，栈顶答案为a[i]，直到栈顶=a[i]或者栈空，a[i]入栈。
观察一下可以发现，这个单调栈的栈顶到栈底是单调递增的，所以出栈顺序是单调递增的。因为有刚刚的后方对前方的影响，所以每次更新的答案也是对的。
class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { stack<int>sta; int n=nums2.size(); int m=nums1.size(); vector<int>ans(m,-1); unordered_map<int,int>mp; for(int i=0;i<n;i++) { while(!sta.empty()) { int now=sta.top(); if(now<nums2[i]) { mp[now]=nums2[i]; sta.pop(); } else break; } sta.push(nums2[i]); } while(!sta.empty()) { int now=sta.top();sta.pop(); mp[now]=-1; } for(int i=0;i<m;i++) { ans[i]=mp[nums1[i]]; } return ans; } };
有另一个类似的题是：每日温度，可以试试。
借着这个思路，看下一道题
接雨水
这也是一个经典题。给你一些竖着的墙，问你最多能接的雨水是多少：
按照刚刚的思路，后面的墙对前面的墙的影响是单调的，这个就像括号匹配一样。后面的墙是右括号，前面的墙是左括号，两边去做匹配。但是这个题不一样的是，这里面的墙除了对前面有影响外，可能还会对后面有影响！因此，我们在计算答案的时候，必须保证从栈中弹出的元素的左右侧影响都考虑过了。
还是和刚刚一样，栈顶到栈底元素单调递增，出栈顺序单调递增。只不过，策略略有不同：
- 如果栈顶a[j]>=a[i]，那么栈顶与a[i]可能形成积水，入栈。
- 如果栈顶a[j]<a[i]，那么:
- 先把a[j]出栈
- 新栈顶a[k]一定大于a[j]，计算以a[j]为底面，a[k]和a[i]围成的水域大小。这个时候a[k]有可能等于a[j]的，大小就是0。
- 把a[i]入栈。
整体上没什么不同，只不过这个是要在固定右侧即将入栈的元素之后，去看栈内的两个元素，比下一个更大的数字多看一层。
class Solution { public: int trap(vector<int>& height) { stack<int>st; int ans=0; for(int i=0;i<height.size();i++) { while(!st.empty()&&height[st.top()]<height[i]) { int s=st.top();st.pop(); if(st.empty())break; int l=st.top(); int r=i; ans+=(r-l-1)*(min(height[r],height[l])-height[s]); } st.push(i); } return ans; } };
另一个类似的题是：柱状图中的最大矩形，可以试试
类型2：类似单调队列，维护值，弹出无用元素
移掉 K 位数字
给你一个数字，要求你移除掉里面的k个数字(可以不连续)，剩下的数字组成的数最小。
这个题要先观察到一个性质：对于i<j，如果a[i]>=a[j]，那么一定删a[i]而不是删a[j]。很显然的，删高位的大数总比删低位小数的强。
利用这个性质，我们维护一个从栈顶到栈底单调递减的栈(尽量保留高位小数)，遍历数组，当a[i]大于栈顶，则入栈。如果a[i]小于等于栈顶，且当前还没有删够k个数字，则弹栈。最后如果还没删够k个或者有前导0，需要做下特殊处理。
class Solution { public: string removeKdigits(string num, int k) { int n=num.length(); stack<int>sta; for(int i=0;i<n;i++) { int now=num[i]-'0'; while(!sta.empty()) { int x=sta.top(); if(x>now&&k>0) { sta.pop(); k--; } else break; } sta.push(now); } string ans; while(!sta.empty()&&k) { k--; sta.pop(); } while(!sta.empty()) { ans += sta.top() + '0'; sta.pop(); } while(ans.length()>0&&ans.back()=='0') { ans.pop_back(); } if(ans.length()==0) { ans+='0'; } reverse(ans.begin(), ans.end()); return ans; } };
132模式
题意：给一个数组，问是否存在i<j<k且a[i]<a[k]<a[j]，也就是132模式，1最小，3最大，2中间。
一个解法是从左到右遍历数组，维护左侧最小值作为a[i]，当前枚举的值作为a[j]，用一个set维护左侧序列，尝试二分找有没有比a[j]大的，如果能找到则返回true。我第一次做这个题也是用的这个解法。
另一个解法就是单调栈了。考虑从右到左枚举a[i]，倘若能维护a[k]和a[j]，就能得到结果了。我们可以用单调栈在维护a[j]的同时更新a[k]。搞一个从顶到底单调递增的栈，作为候选的a[k](越小的a[k]且越大的k(下标)，越有可能被选，所以单调栈在这里很科学)，然后我们再维护一个max_k，作为右侧所有可以作为a[k]的元素中最大的的那个。
当我们枚举到a[i]时，考虑三件事：
- a[i]是不是小于max_k，如果是，则直接返回true。因为如果有a[k]被选中，那必有a[j]在中间，所以132序列存在
- 考虑a[i]当a[j](最大数)。那么对于栈内元素来说，只要是比当前元素(a[j])小的，都可以作为a[k]来使用，于是弹栈，更新max_k。
- 考虑a[i]作为候选a[k]的可能性，a[i]必须大于max_k才有可能成为候选k，否则你这个a[k]的下标又不靠后，元素的值也不够大，不会成为k的。如果能成为候选k，则入栈。
思路清晰，代码：
class Solution { public: bool find132pattern(vector<int>& nums) { stack<int>st; int n=nums.size()-1; int mx_k=-0x7fffffff; for(int i=n;i>=0;i--) { if(nums[i]<mx_k)return true; if(st.empty()) { st.push(nums[i]); continue; } while(!st.empty()&&nums[i]>st.top()) { mx_k=st.top(); st.pop(); } if(nums[i]>mx_k) { st.push(nums[i]); } } return false; } };
类型3：栈内二分(决策单调性优化dp)
这种就比较难了，一般和DP相关，可以先略了。
TBD