单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。朴素的单调栈是帮助我们找到左边或者右边「最近」的数
本文就通过几道算法题来看看单调栈模板的使用。
单调栈模板
首先，看一下 Next Greater Number 的原始问题，这是力扣第 496 题「下一个更大元素 I」：
给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。
函数签名如下：
vector<int> nextGreaterElement(vector<int>& nums);比如说，输入一个数组nums = [2,1,2,4,3]，你返回数组[4,2,4,-1,-1]。
解释：第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。
这道题的暴力解法很好想到，就是对每个元素后面都进行扫描，找到第一个更大的元素就行了。但是暴力解法的时间复杂度是O(n^2)。
这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。
这个情景很好理解吧？带着这个抽象的情景，先来看下代码。
vector<int> nextGreaterElement(vector<int>& nums) {
vector<int> res(nums.size()); // 存放答案的数组
stack<int> s;
// 倒着往栈里放
for (int i = nums.size() - 1; i >= 0; i--) {
// 判定个子高矮
while (!s.empty() && s.top() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的 next great number
res[i] = s.empty() ? -1 : s.top();
//
s.push(nums[i]);
}
return res;
}这就是单调队列解决问题的模板。for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了。
这个算法的时间复杂度不是那么直观，如果你看到 for 循环嵌套 while 循环，可能认为这个算法的复杂度也是O(n^2)，但是实际上这个算法的复杂度只有O(n)。
分析它的时间复杂度，要从整体来看：总共有n个元素，每个元素都被push入栈了一次，而最多会被pop一次，没有任何冗余操作。所以总的计算规模是和元素规模n成正比的，也就是O(n)的复杂度。
问题变形
单调栈的使用技巧差不多了，来一个简单的变形，力扣第 1118 题「一月有多少天」：
给你一个数组T，这个数组存放的是近几天的天气气温，你返回一个等长的数组，计算：对于每一天，你还要至少等多少天才能等到一个更暖和的气温；如果等不到那一天，填 0。
函数签名如下：
vector<int> dailyTemperatures(vector<int>& T);比如说给你输入T = [73,74,75,71,69,76]，你返回[1,1,3,2,1,0]。
解释：第一天 73 华氏度，第二天 74 华氏度，比 73 大，所以对于第一天，只要等一天就能等到一个更暖和的气温，后面的同理。
这个问题本质上也是找 Next Greater Number，只不过现在不是问你 Next Greater Number 是多少，而是问你当前距离 Next Greater Number 的距离而已。
相同的思路，直接调用单调栈的算法模板，稍作改动就可以，直接上代码吧：
vector<int> dailyTemperatures(vector<int>& T) {
vector<int> res(T.size());
// 这里放元素索引，而不是元素
stack<int> s;
/* 单调栈模板 */
for (int i = T.size() - 1; i >= 0; i--) {
while (!s.empty() && T[s.top()] <= T[i]) {
s.pop();
}
// 得到索引间距
res[i] = s.empty() ? 0 : (s.top() - i);
// 将索引入栈，而不是元素
s.push(i);
}
return res;
}数组遍历方向
构建单调栈时候，数组遍历方向取决于每次入栈的元素需要排除左边比它小的元素还是右边。待排除的数在左边就是顺序入栈，右边就是倒序入栈。
再来看一道Bad Hair Day：
Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads.
Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.
Consider this example:
=
= =
= - = Cows facing right -->
= = =
= - = = =
= = = = = =
Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow's hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow's hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!
Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.
题意:给定n头牛的高度，设d(i)为第i头牛可以看到(向右看)的其它牛的总数。
思路:反过来想，求第i头牛可以被左边多少头牛看到。维护一个单调栈即可。
这里需要保留每头牛被左边多少头牛看到的信息，所以这次需要从前往后遍历。即每头牛入栈前往左看，去除小于等于它的元素。等于是因为只有比它高的牛才能看到它，所以高度一样的牛依然需要排除在外
#include<iostream>
#include<vector>
#include<stack>
#include<utility>
using namespace std;
int main(int argc, char** argv){
int N;
cin>>N;
long total = 0;
int j = 0;
vector<int> h(N);
while(cin>>h[j]) j++;
stack<int> s;
for(int i = 0;i<N;i++){
while(!s.empty()&&s.top()<=h[i]){
s.pop();
}
total+=s.size();
s.push(h[i]);
}
printf("%lld",total);
return 0;
}单调栈讲解完毕，下面开始另一个重点：如何处理「循环数组」。
如何处理环形数组
同样是 Next Greater Number，现在假设给你的数组是个环形的，如何处理？力扣第 503 题「下一个更大元素 II」就是这个问题：
比如输入一个数组[2,1,2,4,3]，你返回数组[4,2,4,-1,4]。拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4。
一般是通过 % 运算符求模（余数），来获得环形特效：
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
print(arr[index % n]);
index++;
}这个问题肯定还是要用单调栈的解题模板，但难点在于，比如输入是[2,1,2,4,3]，对于最后一个元素 3，如何找到元素 4 作为 Next Greater Number。
对于这种需求，常用套路就是将数组长度翻倍：
这样，元素 3 就可以找到元素 4 作为 Next Greater Number 了，而且其他的元素都可以被正确地计算。
有了思路，最简单的实现方式当然可以把这个双倍长度的数组构造出来，然后套用算法模板。但是，我们可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。
直接看代码吧：
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
stack<int> s;
// 假装这个数组长度翻倍了
for (int i = 2 * n - 1; i >= 0; i--) {
// 索引要求模，其他的和模板一样
while (!s.empty() && s.top() <= nums[i % n])
s.pop();
res[i % n] = s.empty() ? -1 : s.top();
s.push(nums[i % n]);
}
return res;
}注意，这里结果赋值为res[i % n]，就是会覆盖前一次循环数组结果，以取得最终第一个循环体的结果。这样，就可以巧妙解决环形数组的问题，时间复杂度O(N)。
剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3示例 1：
输入: [1,6,3,2,5]
输出: false示例 2：
输入: [1,3,2,6,5]
输出: true解题思路
本题除了常规的递归分治方法外，还可以借助单调栈判断二叉搜索树。
后序遍历倒序： [ 根节点 | 右子树 | 左子树 ] 。类似 先序遍历的镜像 ，即先序遍历为 “根、左、右” 的顺序，而后序遍历的倒序为 “根、右、左” 顺序。
设后序遍历倒序列表为 \([r\_{n}, r\_{n-1},...,r\_1]\)，遍历此列表，设索引为 \(i\) ，若为 二叉搜索树 ，则有：
- 当节点值 \(r\_i > r\_{i+1}\) 时： 节点 \(r\_ir\)一定是节点 \(r\_{i+1}\)的右子节点。
- 当节点值 \(r\_i < r\_{i+1}\)时： 节点 \(r\_i\) 一定是某节点 \(root\) 的左子节点，且 \(root\) 为节点\( r*{i+1}, r*{i+2},..., r\_{n}\)中值大于且最接近 \(r\_i\)的节点（∵ \(root\)直接连接 左子节点 \(r\_i\)）。
- 当遍历时遇到递减节点 \(r\_i < r\_{i+1}\)，若为二叉搜索树，则对于后序遍历中节点 \(r\_i\)右边的任意节点 \(r\_x \in [r\_{i-1}, r\_{i-2}, ..., r\_1]\)，必有节点值 \(r\_x < root\)。节点 \(r\_x\)只可能为以下两种情况：① \(r\_x\) 为 \(r\_i\)的左、右子树的各节点；② \(r\_x\)为 \(root\)的父节点或更高层父节点的左子树的各节点。在二叉搜索树中，以上节点都应小于 \(root\) 。
- 遍历 “后序遍历的倒序” 会多次遇到递减节点 \(r\_i\)，若所有的递减节点 \(r\_ir\) 对应的父节点 \(root\) 都满足以上条件，则可判定为二叉搜索树。
总而言之：当前元素压入栈时，若其比栈顶元素小，此时根据后序遍历的规则，应遍历到了当前根节点（root）的左子树的左子节点之一（右子节点都会比当前栈顶元素大，会被压入栈），且栈中比它大的最小元素是其父节点，将其值赋给root后，因之后遍历的都是root的左子树上的节点了，所以如果此时出现比root大的元素的话，就不符合二叉搜索树的定义了
根据以上特点，考虑借助 单调栈 实现：
- 借助一个单调栈
stack存储值递增的节点； - 每当遇到值递减的节点 \(r\_i\)，则通过出栈来更新节点
的父节点
； - 每轮判断 \(r\_i\)和 \(root\) 的值关系：
若 \(r\_i > root\)则说明不满足二叉搜索树定义，直接返回false。
若 \(r\_i < root\)则说明满足二叉搜索树定义，则继续遍历。
代码
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
stack<int> s;
int root = INT_MAX;
for(int i= postorder.size()-1;i>=0;--i){
if(postorder[i]>root) return false;
while(!s.empty()&&s.top()>postorder[i]){
root=s.top();
s.pop();
}
s.push(postorder[i]);
}
return true;
}
};