单调栈与其说是一类题的解法,倒不如说是一个缩小时间复杂度的工具。
因为能用单调栈解决的题,咱们用朴素一些的方式基本也都是可以想出来的。单调栈只是加速这个过程
一个特点是单调
另一个特点就是多对一
如果有两个影响因素,那么我们需通过排序排除掉一个
例如因素有距离和到终点的时间,那么我们先对距离排序,再对到终点的时间使用单调栈即可
42.接雨水
https://leetcode.cn/problems/trapping-rain-water/
单调性:柱子单调递增或者单调递减的时候都是接不到雨水的
多对一:一个位于水洼右侧的柱子可以对应左侧多个柱子
402.移掉K位数字
https://leetcode.cn/problems/remove-k-digits/
单调性:数字排位上是单调递增的
多对一:一个较小的元素可以“干掉”多个比他大的数字
503下一个更大元素2
https://leetcode.cn/problems/next-greater-element-ii/
单调性:要找更大的元素,必然会有区域性的单调递减
多对一:可能很多元素的下一个更大元素是同一个元素
1475. 商品折扣后的最终价格
https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/
同上
853. 车队
单调性:单调递减一般是后面的元素比前面小,在这个题中我们替换一下概念,后面的车追不上前面的车,这何尝不是一种单调性呢?
多对一:一辆前车可以拦住很多辆后面的车
排除影响因素:通过对距离终点的距离进行排序,使得我们只需要关注车辆到达终点还需要的时间这一个变数
975. 奇偶跳
需要求任意一个点下一次奇数跳会跳到哪里,以及偶数跳要跳到哪里
以奇数跳为例
单调性:每次都要跳到一个更大的数上面,且必须向后跳。这两点都有单调性的特点
多对一:多个点的下一次奇数跳可能在同一个位置
排除影响因素:对数值排序,就只需要关注有没有向后跳这一个因素了