引入
有时我们希望求出往前第一个比自己大的数。
形式化的说：给一个数组 \(a\)，求一个数组 \(p\)，使得 \(a_{p(i)}>a_i\) 且 \(\forall p_i<j<i,a_j\le a_i\)。若不存在 \(p_i\)，\(p_i\gets i\)。
怎么求呢？
暴力
首先考虑最朴素的做法。对于每一个 \(i\)，向前枚举 \(j<i\)，若 \(a_j>a_i\)，\(p_i\gets j\)。
当 \(a\) 降序时，复杂度达到上界，为 \(O(n^2)\)，不够优秀。
单调栈
聪明的算法经常都是优化\观察暴力得来的，于是观察暴力出的 \(p\) 数组。有以下例子：
| id | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| \(a\) | \(3\) | \(2\) | \(4\) | \(1\) | \(1\) |
| \(p\) | \(1\) | \(1\) | \(3\) | \(3\) | \(3\) |
可以发现，\(p_1=p_2=1\)，而到 \(p_3\) 时却为 \(3\)。为什么呢？因为 \(a_3>a_1\)，于是 \(p_3=p_4=p_5=3\)，都找 \(3\) 去了。
可以看下面这张图理解：
问题来了，如果只挡住一个，后面山外有山有更高的怎么办？维护一个栈即可，我们叫他单调栈（因为栈中单调）。
操作
可以将这个单调栈 \(stk\) 想象为 OI 队。栈中保存 \(a\) 中下标即可。其中满足 \(1\le i<n,stk_i<stk_{i+1}, a_{stk(i)}>a_{stk(i+1)}\)。即年龄从大到小（下标从小到大），实力也从大到小。每次添加一个 \(a_i\)，都要卷死 \(stk\) 中的幸运 oier。
- 出栈。如果有学长比你（\(i\)）弱，ta 就可以 AFO 了。（\(a_{stk(back)}\le a_i\)，那么退栈。）
- 入栈。如果学长们都比你强，你就淘汰不了 ta 们，于是你（\(i\)）入栈。
这样就保证了 OI 队中实力单调下降。
那么讲了半天 \(p_i\) 怎么求？注意到入栈时学长都比你强，那么 ta 们中最小的就是所求的 \(p_i\)。
由于每个 \(a_i\) 顶多入栈、出栈各一次，故时间复杂度 \(O(n)\)。
单调队列
其实相比单调栈没改多少。注意到每个 oier 迟早得退役，那么有时可能会规定 \(a_i\) 必须出队的时间。维护单调队列时每次判断队首元素是否需要出队即可。注意单调队列是双端队列，需要队首出，队尾进出。
习题
板子就不列了。
-
P1901 发射站 - 洛谷 较板。
-
P7167 [eJOI2020 Day1] Fountain - 洛谷 很妙的一题，需要结合其他算法。
-
P2422 良好的感觉 - 洛谷 依然很妙。需要巧妙地枚举。
-
P1823 [COI2007] Patrik 音乐会的等待 - 洛谷 没做过，有时间做一下。
后记
如果是单调不降或上升等同理。