单调栈算法题型总结

单调栈与其说是一类题的解法，倒不如说是一个缩小时间复杂度的工具。
因为能用单调栈解决的题，咱们用朴素一些的方式基本也都是可以想出来的。单调栈只是加速这个过程

一个特点是单调
另一个特点就是多对一

如果有两个影响因素，那么我们需通过排序排除掉一个
例如因素有距离和到终点的时间，那么我们先对距离排序，再对到终点的时间使用单调栈即可

https://leetcode.cn/problems/trapping-rain-water/
单调性：柱子单调递增或者单调递减的时候都是接不到雨水的
多对一：一个位于水洼右侧的柱子可以对应左侧多个柱子

https://leetcode.cn/problems/remove-k-digits/
单调性：数字排位上是单调递增的
多对一：一个较小的元素可以“干掉”多个比他大的数字

https://leetcode.cn/problems/next-greater-element-ii/
单调性：要找更大的元素，必然会有区域性的单调递减
多对一：可能很多元素的下一个更大元素是同一个元素

单调性：单调递减一般是后面的元素比前面小，在这个题中我们替换一下概念，后面的车追不上前面的车，这何尝不是一种单调性呢？
多对一：一辆前车可以拦住很多辆后面的车
排除影响因素：通过对距离终点的距离进行排序，使得我们只需要关注车辆到达终点还需要的时间这一个变数

需要求任意一个点下一次奇数跳会跳到哪里，以及偶数跳要跳到哪里
以奇数跳为例
单调性：每次都要跳到一个更大的数上面，且必须向后跳。这两点都有单调性的特点
多对一：多个点的下一次奇数跳可能在同一个位置
排除影响因素：对数值排序，就只需要关注有没有向后跳这一个因素了