1.什么是单调栈
单调栈是一种简单数据结构，顾名思义，就是单调递增（或递减）的栈。
2.单调有什么用？
单调意味着数据是有序的，数据变化是没有“回头路”的，一路走到底，此外，最重要的特性之一就是能够快速地找到最大值或者最小值。
【单调递增性函数图】
/pub/YDOvOV-NegE3Nk)
【单调递增栈】
/pub/5OVxmk-1mmx5r7)
3.应用场景
最经典的案例就是运用单调栈在一个序列中求每个元素左边（或右边）第一个比它小（或大）的元素，其实就是求在单调栈中的最值，在遍历过程中时刻维护栈的单调性，那么每个元素对应栈中的最值就是答案。
具体实现可以使用数组模拟栈或者调用库函数（如C++的STL）
4.举个例子
【题目描述】
给出项数为n的整数数列 a1，a2，a3，... ，an。
定义函数 f(i) 代表数列中第i个元素之后第一个大于ai的元素的下标，若不存在，则 f(i)=0。
试求出f(1,2,3,...n)。
【输入格式】
第一行一个正整数n
第二行n个正整数a1,a2,...,an
【输出格式】
一行n个整数f(1,2,...,n)的值。
【输入样例】
5
1 4 2 3 5
【输出样例】
2 5 4 5 0
【数据范围】
1≤n≤3e6, 1≤ai≤1e9
思路：简单来说就是求每一个元素右边第一个比它大的元素下标，符合单调栈的应用场景。由于是求右边的元素下标，因此首先我们需要从右往左遍历，求比它大的元素且从右向左遍历，因此栈中应该保持单调递减性，使用单调递减栈。
样例分析：
【第1步】下标为5的元素是5，栈为空，没有比它大的元素，依题意输出0即可，再将下标5放入栈中（注意下标从1开始）
【第2步】下标为4的元素是3，小于栈顶元素5，满足单调递减性，不需要弹出栈顶，将栈顶下标5放入结果集，再将下标4放入栈中
【第3步】下标为3的元素是2，小于栈顶元素3，满足单调递减性，不需要弹出栈顶，将栈顶下标4放入结果集，再将下标3放入栈中
【第4步】下标为2的元素是4，大于栈顶元素2，不满足单调递减性，弹出栈顶后继续判断，此时栈顶元素为3，仍然不满足单调递减性，因此继续弹出栈顶，新的栈顶元素为5，大于4，（终于）满足单调递减性，不需要弹出栈顶，直接将栈顶下标5放入结果集，再将当前的下标2放入栈中
【第5步】下标为1的元素是1，小于栈顶元素4，满足单调递减性，不需要弹出栈顶，将栈顶下标2放入结果集，再将下标1放入栈中
【第6步】遍历结束，输出结果集
C++代码实现
#include<iostream>
using namespace std;
const int N = 3e6 + 10;
// n为序列长度，sta[]为模拟栈，tt为栈顶指针，a[]为输入序列，res[]存放结果集
int n, sta[N], a[N], tt, res[N];
int main()
{
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i]; //输入序列
for(int i=n; i>=1; i--) //从右往左遍历
{
while(tt && a[i] >= a[sta[tt]]) tt --; //栈不能为空的情况下不满足单调性就弹出栈顶
if(tt) res[i] = sta[tt]; //栈不为空的情况下，将当前栈顶放入结果集
else res[i] = 0; //若栈为空，说明不存在比当前元素大的元素，依题意将0放入结果集
sta[++ tt] = i; //动态地将当前元素存入栈中
}
//可以发现，整个过程都在维护栈的单调性
for(int i=1; i<=n; i++) cout << res[i] << " "; //输出结果，大功告成
cout << endl;
return 0;
}
5.实战 直方图中最大的矩形
来源：《算法竞赛进阶指南》
【题目描述】
直方图是由在公共基线处对齐的一系列矩形组成的多边形。
矩形具有相等的宽度，但可以具有不同的高度。
例如，图例左侧显示了由高度为 2,1,4,5,1,3,3 的矩形组成的直方图，矩形的宽度都为 1:
/pub/6dre2v-e3z0mzV)
通常，直方图用于表示离散分布，例如，文本中字符的频率。
现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。
图例右图显示了所描绘直方图的最大对齐矩形。
【输入格式】
输入包含几个测试用例。
每个测试用例占据一行，用以描述一个直方图，并以整数 nn 开始，表示组成直方图的矩形数目。
然后跟随 n 个整数 h1，... ,hn。
这些数字以从左到右的顺序表示直方图的各个矩形的高度。
每个矩形的宽度为 1。
同行数字用空格隔开。
当输入用例为 n=0 时，结束输入，且该用例不用考虑。
【输出格式】
对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。
每个数据占一行。
请注意，此矩形必须在公共基线处对齐。
【输入样例】
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
【输出样例】
8
4000
【数据范围】
1≤n≤1000001≤n≤100000, 0≤hi≤1000000000
思路分析：首先观察直方图很容易发现，每个x坐标对应的矩形条高度就是最大矩形的极限高度，而极限宽度则取决于左边能够延伸到哪里，右边能延伸到哪里。在高度能够确定的情况下，求面积只需要确定最大宽度，而求最值可以使用单调栈的思想。令每个矩形条向左延伸，直至碰到第一个比它矮的矩形条，将其坐标存入左极限集；向右延伸，直至碰到第一个比它矮的矩形条，将其坐标存入右极限集。最后遍历x轴的每个矩形条，求出每个矩形条对应的面积：高度*（右极限-左极限-1），取最大即可。
C++代码实现
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, h[N], l[N], r[N], sta[N]; //l[]为左极限集，r[]为右极限集, sta[]为模拟栈
int main()
{
while(cin >> n, n)
{
h[0] = h[n+1] = -1;
for(int i=1; i<=n; i++) cin >> h[i];
int tt = 0;
sta[0] = 0;
for(int i=1; i<=n; i++) //从左往右遍历，求每个x的左极限
{
while(h[i] <= h[sta[tt]]) tt --;
l[i] = sta[tt];
sta[++ tt] = i;
}
tt = 0;
sta[0] = n + 1;
for(int i=n; i; i--) //从右往左遍历，求每个x的右极限
{
while(h[i] <= h[sta[tt]]) tt --;
r[i] = sta[tt];
sta[++ tt] = i;
}
LL res = 0;
for(int i=1; i<=n; i++)
res = max(res, (LL)h[i] * (r[i] - l[i] - 1)); //矩形面积公式
cout << res << endl;
}
return 0;
}
这里有道力扣的面试题，跟上面的实战题类似，没想到在力扣里的难度是困难题，在竞赛里其实只是一道简单题= =
6.最后的话
上面的C++代码实现中的数组模拟栈可以换成库函数中的栈，思路是一样的。
你学fei了吗？
（转载请注明出处，侵权必究）
