题目描述
简介
感觉简介越来越难写了 = =
我们还是先写几个定义吧
前缀最大值：当 $a_i$ 在区间 $[l,r]$ 中不存在 $l \le j < i , a_j > a_i$
一个比较显然的东西，从前往后扫的单调队列和单调栈都是维护的后缀最大或者最小值
应用
滑动窗口
这好像是单调队列最基本的应用了吧
大概就是我们枚举窗口的右端点，因为窗口是向右滑的，所以每次加入的数如果既小又靠后，那么前面那些数肯定没用了
求一个数左边/右边第一个大于/小于它的数
Luogu P2947 [USACO09MAR]Look Up S
我们考虑单调栈，不妨考虑求右边第一个大于它的数
大概就是把每个数 $push$ 到栈里，并且把比它小的数扔掉，在扔掉的时候记录被扔掉的数的右边第一个大于它的数就是要进栈的这个数
求所有满足 $i<j,\forall k\in [i+1,j-1],a_k\le a_i,a_k \le a_j$ 的 $(i,j)$ 的个数
我们枚举所有的 $j$，注意到所有满足条件的 $i$ 一定是 $pre[j-1]$ 的后缀最大值
这个东西直接拿单调栈维护即可，权值相同的需要特殊处理
求最长的最大值最小值相差不超过 k 的序列
Luogu P3512 [POI2010]PIL-Pilots
大概就是对于考虑左端点右移的过程中，符合条件的左端点要么不动，要么右移
我们考虑如果右移的话会移动到什么位置，显然是移动到区间内的最大值或者最小值更新的时候
当然这个东西可以拿很多数据结构来维护，这里我们考虑用单调队列来维护最大值或者最小值更新的位置
这个位置显然就是我们单调队列中维护的所有后缀最小/最大值
求一个 $01$ 矩阵中面积最大的全 $1$ 矩阵
我们枚举矩阵的最后一行，然后对于这一行每个位置处理出向上最长连续 $1$ 的长度
然后我们考虑对于每一列，我们求它作为最小值的时候的最长区间，那这个区间和它的长度相乘就是它的答案
我们对于所有列都求一遍答案即可，找它自己作为最小值的区间可以用单调栈