单调栈就是在栈的基础上保持了数的有序。
最常见的应用是用来求一个序列/数组中，每个数的左边/右边第一个比其小/大的数的位置。
例如找一个数组中每一个数的前面最近的比其小的数：
4, 6, 8, 7, 5
首先维护一个栈stk，从前往后找每个数的答案，在找7这个数的时候，此时栈中已经保存了4, 6, 8这三个数了，首先比较栈顶元素8，大于7，弹栈，以后8不会再是7后面的任意一个数的答案，因为7<8，而且7距离它们更近。然后比较下一个数6<7，即7的答案是6，然后将7入栈供后面的数比较。
基于此，在找后面数的答案的时候就不需要再与8进行比较了，如果数据量比较大(例如4, 6, 8, 8, 8, 8, 8, ..., 8, 7, 5, ...，7的后面的数不会再与8进行比较)，将会节省很大一部分时间。
因此可以发现栈stk中的每个数是严格按照递增的顺序的，所以称为单调栈。
// 求右边第一个比其大的数
vector<int> ans(T.size(), 0);
stack<int> s;
for(int i = 0; i < T.size(); i ++ )
{
while(!s.empty() && T[s.top()] < T[i])
{
ans[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
// 求右边第一个比其小的数
vector<int> ans(T.size(), 0);
stack<int> s;
for(int i = 0; i < T.size(); i ++ )
{
while(!s.empty() && T[s.top()] > T[i])
{
ans[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
// 求左边第一个比其大的数
vector<int> ans(T.size(), 0);
stack<int> s;
for(int i = T.size() - 1; i >= 0; i -- )
{
while(!s.empty() && T[s.top()] < T[i])
{
ans[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
// 求左边第一个比其小的数
vector<int> ans(T.size(), 0);
stack<int> s;
for(int i = T.size() - 1; i >= 0; i -- )
{
while(!s.empty() && T[s.top()] > T[i])
{
ans[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
参考题：
https://www.acwing.com/video/258/
https://leetcode-cn.com/problems/daily-temperatures/
https://leetcode-cn.com/problems/next-greater-element-i/
https://leetcode-cn.com/problems/maximum-subarray-min-product/