单调栈和单调队列

单调栈

适用问题：处理给定数列确认每个数的左（右）边第一个比它小（大）的数

例如： LeetCode 84. 柱状图中最大的矩形 和 LeetCode 42. 接雨水

原子问题：给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数的下标（从0开始标号），如果不存在则输出 −1。

实现：

1. 遍历数组，当遍历到第 $i$ 个数 $x_i$ 时，查看栈顶元素
2. 如果栈顶元素大于或等于 $x_i$ 也意味着栈顶元素与 $x_i$ 相比毫无优势，因为 $x_i$ 离未遍历到的元素距离与当前栈顶元素相比都要更近，并且其值也满足比栈顶元素更具优势，即栈顶元素当前一定不会被后面的元素匹配上
3. 继续重复过程以弹出栈中不比 $x_i$ 小的老旧值（淘汰老人，残酷的羚羊飞渡）这样一来栈顶永远放着 最新但不小 的值
4. 这时如果栈为空即在其左方找不到比 $x_i$ 小的数输出为-1，否则输出栈顶元素
5. 将 $x_i$ 压如栈顶
6. 重复此过程得到的栈是单调递增的即栈是升序排列的故称之为单调栈

单调队列

适用问题：查找可滑动窗口内的最大值与最小值（俗称滑动窗口问题）

例如：LeetCode 239. 滑动窗口最大值

原子问题：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

实现：

1. 遍历数组，当遍历到第 $i$ 个数 $x_i$​ 时，查看队头原始是否超出了滑动窗口的范围，如果是超过范围就弹出
2. 如果 $x_i$ 大于队尾元素，也就意味着对于这个队尾元素的存在周期内与 $x_i$ 相比没有任何优势因为 $x_i$ 比队尾元素新不会在队尾元素弹出窗口前被弹出，而且 $x_i$ 的值也比队尾元素更具优势即宁可选择 $x_i$​ 也不会选上队尾元素
3. 重复此过程以弹出队列中不比 $x_i$ 大的弱值（优胜劣汰，无奈的自然选择）这样一来队头永远放着 最大但旧 的值
4. 需要先将当 $x_i$​ 加入当前队尾以避免队列为空的问题
5. 输出队头元素
6. 重复此过程得到的队列是单调递减的故称为单调队列

---

单调栈与单调队列的对比

单调栈是求某个大值但它必须最新，单调队列是求某个新值但它必须最大，两者的侧重点不同， 栈和时序绑定，队列和权重绑定；

单调栈与单调队列都用到了提前排除某些不可能的值的思想；

依靠新值的添加与不合适值的弹出维持了很好的有序性