单调栈

一种基于 栈 的数据结构, 保证栈底到栈顶的单调性
以下以栈底到栈顶为单调减来讲解

我们有一个单调栈, 在从左到右扫描数组的情况下将数组元素入栈, 同时为了保证单调性, 在每个元素入栈前需要先从栈顶弹出不符合单调性的元素
可以使用单调递减的单调栈来求每个元素右侧第一个不小于它的值

示例

[0]
arr: 5 4 3 2 4  
stk: 

[1]
arr: 4 3 2 4  
stk: 5  

[4]
arr: 4
stk: 5 4 3 2  

[5]
arr: 
stk: 5 4   
pop: 2 3 4  
因此 arr[1..3](4, 3, 2) 的元素的右侧第一个不小于它的值都是 arr[4](4)  

[6] 
stk: 5 4
扫描完成, arr[0](5) 和 arr[4](4) 的右侧都没有不小于它的值

通常在实际应用的时候栈里面存下标, 通过下标访问数组元素来比较大小
从左到右 和 从右到左 扫两遍可以求得一个数作为最小值的区间范围

单调队列

本质上是在 单调栈 的栈底开了一个口, 把过期的元素弹出
因为要在栈底弹出同时也要在栈顶弹出, 所以以 双端队列 作为储存的基础

可以用来求固定长度滑动窗口的最值