什么是單調(diào)棧草慧？
1.單調(diào)遞增棧：
棧頂 到 棧底 數(shù)據(jù)從小到大勾缭，遇到比棧頂大的數(shù)就彈棧
數(shù)據(jù)： [2, 1, 3, 5, 4]
比如：
第一步： 2 入棧
第二步：1入棧
第三步：3入棧犀概，大于棧頂1综看，1出棧； 又大于棧頂2馒索，2出棧莹妒，棧內(nèi)只有3
image-20210401103312684.png
依次類推：
最后棧內(nèi) 只剩下 5 4
image-20210401105153905.png
2.單調(diào)遞減棧：
棧頂 到 棧底 數(shù)據(jù)從大到小，遇到比棧頂小的數(shù)就彈棧
K 數(shù)題 單調(diào)棧解法
以時間復(fù)雜度O(n)從長度為n的數(shù)組中找出同時滿足下面兩個條件的所有元素：
（1）該元素比放在它左邊的所有元素都大绰上；
（2）該元素比放在它右邊的所有元素都小
數(shù)據(jù)： [2, 1, 3, 5, 4] 旨怠，result 為 3
分析：
（1）單調(diào)遞增數(shù)組肯定滿足條件, 如[1, 2, 3, 4, 5]，也就是單調(diào)遞減棧
（2）維護(hù)一個棧蜈块，僅僅是單調(diào)遞減是不夠的鉴腻，元素入棧的時候只能保證比棧內(nèi)的數(shù)據(jù)都大，但是不能保證比之前（已經(jīng)出棧的）數(shù)據(jù)大
（3）需要維護(hù)一個最大值疯趟，來判斷當(dāng)前元素 左邊是否有 比自己大的元素
步驟： 當(dāng)前元素與 max 相比，只有比 max 大的 才可以入棧
（1） 2 入棧谋梭， max = 2信峻， 數(shù)組為[2]
（2）1 小于 2，開始彈棧瓮床， 2 彈出盹舞， max = 2 ，數(shù)組為 []
（3）3 入棧隘庄， max = 3踢步， 數(shù)組為[3]
（4）5 入棧， max = 5丑掺， 數(shù)組為[3获印，5]
（5）4 小于 5，開始彈棧街州， 5彈出兼丰，數(shù)組為 [3]
Jietu20210401-114909.jpg
時間復(fù)雜度：O(n)
（1）內(nèi)嵌的 for in 最壞的情況是 （2玻孟，3，4鳍征，5黍翎，6，7艳丛，8匣掸，9，1）O（n）
（2）所以最壞的情況下是 O（2n）氮双，也就是O（n）
代碼
var nums1 = [2, 1, 3, 5, 4]
func getK(_ nums: [Int]) -> [Int] {
var max = Int.min
var res: [Int] = []
for idx in 0..<nums.count {
let cur = nums[idx]
if cur > max {
res.append(cur)
max = cur
} else {
for i in (0..<res.count).reversed() {
if res[i] > cur {
res.remove(at: i)
}
}
}
}
// 去除最后一個滿足條件的數(shù)碰酝，因?yàn)橛疫厸]有元素
if let last = res.last, last == nums.last {
res.removeLast()
}
return res
}
