單調(diào)棧與其說(shuō)是一類題的解法岖妄,倒不如說(shuō)是一個(gè)縮小時(shí)間復(fù)雜度的工具遥昧。
因?yàn)槟苡脝握{(diào)棧解決的題藐俺,咱們用樸素一些的方式基本也都是可以想出來(lái)的兑燥。單調(diào)棧只是加速這個(gè)過(guò)程
一個(gè)特點(diǎn)是單調(diào)
另一個(gè)特點(diǎn)就是多對(duì)一
如果有兩個(gè)影響因素百拓,那么我們需通過(guò)排序排除掉一個(gè)
例如因素有距離和到終點(diǎn)的時(shí)間琴锭,那么我們先對(duì)距離排序,再對(duì)到終點(diǎn)的時(shí)間使用單調(diào)棧即可
42.接雨水
https://leetcode.cn/problems/trapping-rain-water/
單調(diào)性:柱子單調(diào)遞增或者單調(diào)遞減的時(shí)候都是接不到雨水的
多對(duì)一:一個(gè)位于水洼右側(cè)的柱子可以對(duì)應(yīng)左側(cè)多個(gè)柱子
402.移掉K位數(shù)字
https://leetcode.cn/problems/remove-k-digits/
單調(diào)性:數(shù)字排位上是單調(diào)遞增的
多對(duì)一:一個(gè)較小的元素可以“干掉”多個(gè)比他大的數(shù)字
503下一個(gè)更大元素2
https://leetcode.cn/problems/next-greater-element-ii/
單調(diào)性:要找更大的元素衙传,必然會(huì)有區(qū)域性的單調(diào)遞減
多對(duì)一:可能很多元素的下一個(gè)更大元素是同一個(gè)元素
1475. 商品折扣后的最終價(jià)格
https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/
同上
853. 車隊(duì)
單調(diào)性:?jiǎn)握{(diào)遞減一般是后面的元素比前面小决帖,在這個(gè)題中我們替換一下概念,后面的車追不上前面的車蓖捶,這何嘗不是一種單調(diào)性呢地回?
多對(duì)一:一輛前車可以攔住很多輛后面的車
排除影響因素:通過(guò)對(duì)距離終點(diǎn)的距離進(jìn)行排序,使得我們只需要關(guān)注車輛到達(dá)終點(diǎn)還需要的時(shí)間這一個(gè)變數(shù)
975. 奇偶跳
需要求任意一個(gè)點(diǎn)下一次奇數(shù)跳會(huì)跳到哪里,以及偶數(shù)跳要跳到哪里
以奇數(shù)跳為例
單調(diào)性:每次都要跳到一個(gè)更大的數(shù)上面刻像,且必須向后跳畅买。這兩點(diǎn)都有單調(diào)性的特點(diǎn)
多對(duì)一:多個(gè)點(diǎn)的下一次奇數(shù)跳可能在同一個(gè)位置
排除影響因素:對(duì)數(shù)值排序,就只需要關(guān)注有沒(méi)有向后跳這一個(gè)因素了