1. 单调栈
给定一个长度为 \(n\) 的数列 \(a\)，对每个数字求出其右/左边第一个值大于等于它的数字的位置。
考虑从左到右扫整个序列，维护一个栈，里面存放可能成为答案的数字，当遍历到一个新的数 \(a_i\) 的时候，可以发现栈中 \(\leq a_i\) 的数就再也不可能成为答案了，那就把它们弹掉，此时栈顶就是答案，之后加入 \(a_i\)。
由于栈中的元素是单调不升的，故得名单调栈。
这么做的复杂度：每个元素只会入栈出栈一次，所以复杂度是线性的。
点击查看代码
Rep(i,n,1)
{
while(top>0&&a[s[top]]<=a[i]) top--;
ans[i]=s[top];
s[++top]=i;
}
最大值求和
给出一个 \(n\) 个数的序列，对所有 \(1 \leq l \leq r \leq n\) 求 \(\max(a_l,a_{l+1},\dots ,a_{r-1},a_r)\) 并求和。\(n \leq 10^6,a_i \leq 10^3\)。
考虑一个数字会在哪些区间被算到，对于一个数字 \(a_p\)，用单调栈求出左面和右面第一个比它大的位置 \(l_p\) 和 \(r_p\)，那么当 \(l_p < L \leq p \leq R < r_p\) 的时候，区间 \([L,R]\) 的 \(\max\) 就是 \(a_p\)，依据乘法原理，\(a_p\) 的贡献就是 \(a_p \times (p-l_p) \times (r_p-p)\)，求和即可。
注意序列中有相同数字的时候，要钦定（比如）左边的比右边的大。
序列最大价值
给出一个 \(n\) 个数字的序列，求 \(1\leq l \leq r\leq n\) 使得 \((r-l+1) \times \min(a_l,a_{l+1},\dots ,a_{r-1},a_r)\) 最大。\(n \leq 10^6,a_i \leq 10^3\)。
还是和刚才一样对每个数字维护其在哪个极大区间成为最小值，然后算一算即可。
洛谷 P4147 玉蟾宫
有一个矩阵，每个位置是 \(0\) 或者 \(1\)。求最大的全 \(1\) 子矩阵。\(n \times m \leq 10^6\)。
枚举每一行，对每个位置维护其向上极长的 \(1\) 的段的长度，然后每行转化为刚刚那个问题即可。
2. 单调队列
有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
沿用单调栈的思路，从左到右扫描每一个 \(i\)，从栈顶弹数，不过由于栈底的数有可能不在滑动窗口里了，所以还要从栈底弾掉，栈不支持此操作，考虑使用队列。复杂度 \(\mathcal{O}(n)\)。
点击查看代码
l=1,r=0;
For(i,1,n)
{
while(l<=r&&a[q[r]]<=a[i]) r--;
q[++r]=i;
while(l<=r&&i-q[l]>=k) l++;
if(i>=k) cout<<a[q[l]]<<" ";
}