单调栈 and 单调队列学习笔记
本文均以维护单调递增的栈/队列举例。
以后在写动态规划单调队列/单调栈优化的时候，这两个东西会合并。
单调栈
本质上就是模拟。
假设要维护一个单调递增的栈，那么对于一个元素进来了，在栈顶的所有比他小的数我全部都要踢出去，不然就不满足单调性。然后把这个数加到栈里面去。
这里维护的是下标，因为数比较大。不能进行标记。
维护一个单调递增栈，从后往前枚举，每次一个数进来就把小于等于他的数给踢出去，（由于要求第一个大于他的数，当前的位置 \(i\) 是相对于 \([1,i]\) 间的数更近的，相同的情况下 \(i\) 更优）。栈顶就是第一个比他大的数的下标了。
所以，在这个栈里面，数是单调递增的，下标也是单调递增的。故栈顶就是答案。
单调队列
和单调栈的本质基本上是一样的，如果维护一个单调递增的队列，那么一个数加进来的时候就把所有不符合单调性的数全部踢出去。
维护两个单调递增，单调递减队列，如果队列中有数的位置不符合窗口大小，就应该踢出去。
队首就是答案。
标签：下标,队列,递增,踢出去,笔记,维护,单调 From： https://www.cnblogs.com/JuneFailue/p/18118183