四、单调栈
- 单调栈是栈的一种特例，在一般情况下使用较少。
- 单调栈分为单调递增栈和单调递减栈。
- 单调递增栈是栈中元素从栈底到栈顶是递增的。
- 单调递减栈是栈中元素从栈底到栈顶是递减的。
- 应用：求解下一个大于 x 元素或者是小于 x 元素的位置。
给一个数组，返回一个大小相同的数组，返回的数组的第 i 个位置的值应当是，对于原数组中的第 i 个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上 -1 )。
1. 伪代码
stack<int> st; for (遍历这个数组){ if (栈空 || 栈顶元素大于等于当前比较元素){ 入栈; } else{ while (栈不为空 && 栈顶元素小于当前元素){ 栈顶元素出栈; 更新结果; } 当前数据入栈; } }
2. 单调栈的应用
- 左边区间第一个比它小的数，第一个比它大的数。
- 确定这个元素是否是区间最值。
- 右边区间第一个大于它的值。
- 到 右边区间第一个大于它的值的距离。
- 确定以该元素为最值的最长区间。
五、单调队列
- 单调队列是队列的一种特例，在一般情况下使用较少。
- 单调队列中的元素始终保持着单增或者单减的特性。
- 单调队列不只是做到了有序，还可以在每次加入或者删除元素时都保持序列里的元素有序，即队首元素始终是最小值或者最大值。
- 单调队列分为单调递增队列和单调递减队列两种。
- 单调递增队列：保证队列头元素一定是当前队列的最小值，用于维护区间的最小值。
- 单调递减队列：保证队列头元素一定是当前队列的最大值，用于维护区间的最大值。
- 实现单调队列，主要分为三个部分：
去尾操作 ：队尾元素出队列。当队列有新元素待入队，需要从队尾开始，删除影响队列单调性的元素，维护队列的单调性。(删除一个队尾元素后，就重新判断新的队尾元素)。
删头操作 ：队头元素出队列。判断队头元素是否在待求解的区间之内，如果不在，就将其删除。（这个很好理解呀，因为单调队列的队头元素就是待求解区间的极值）。
取解操作 ：经过上面两个操作，取出 队列的头元素 ，就是 当前区间的极值 。
单调队列与普通队列有些不同，因为右端既可以插入又可以删除，因此在代码中通常用一份数组和 两个指针来实现，而不是使用 STL 中的 queue。如果一定要使用 STL ，那么则可以使用双端队列（即两端都可以插入和删除），即deque 。
————————————————
1. 单调队列的应用
- 可以查询区间最值（不能维护区间k大，因为队列中很有可能没有k个元素）。
- 优化DP，单调队列一般是用于优化动态规划方面问题的一种特殊数据结构，且多数情况是与定长连续子区间问题相关联。
2. 与单调栈的异同
2.1 相同点
- 单调队列和单调栈的“头部”都是最先添加的元素，“尾部”都是最后添加的元素。
- 递增和递减的判断依据相同：从栈底（队尾）到栈顶（队首），元素大小的变化情况。所以队列和栈是相反的。
- 两者维护的时间复杂度都是 O(n)，每个元素都只操作一次。
2.2 不同点
单调队列可以从队列头弹出元素，可以方便地根据入队的时间顺序（访问的顺序）删除元素。
单调队列和单调栈维护的区间不同。当访问到第i个元素时，单调栈维护的区间为 [0,i)，而单调队列维护的区间为 (lastpop,i)
单调栈无法获取 [0,i) 的区间最大值/最小值。因为单调队列可以访问“头部”和“尾部”，而单调栈只能访问栈顶（也就是“尾部”）。
