单调栈和单调队列
单调栈
一个无序数组，对于每一个元素 x，找出 x 左边且第一个比它小的数。（找不到则输出 -1）
3 4 2 7 5 => -1 3 -1 2 2
暴力的做法是遍历每个元素，每个元素从右向左依次对比（这里可以用栈实现），时间复杂度为 O(n^2)。
每一个新加入栈的元素 y，如果 y 比前面的某个数 z 小，遍历答案时， z 永远不可能输出。
把 y 压入栈前，把小于等于 y 的数都弹出来，就获得了一个单调栈。（在本题中为严格单调递增）
假设旧栈是单调栈，新栈也必定是单调栈。
单调队列
和单调栈的优化思想一致，先尝试用暴力算法求解，后尝试优化。
给定一个大小为 n 的数组，有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边，每次滑动窗口向右移动一个位置。而你只能在窗口中看到 k 个数字。
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
和单调栈一样，求最小值时：当滑动窗口中的元素为 [3 -1 -3] 时，只要 -3 在队列里，3 和 -1 就不可能是答案。
而且 -3 是后生，在滑动窗口存在的时间也比 3 和 -1 要长。所以完全可以把 3 和 -1 移出队列，这样得到的队列就是严格单调递增的了。（为了保证单调性，从队尾向对头移除）
求最大值同理。