Swift 单调递减栈解决 K数 问题

什么是单调栈？

1.单调递增栈：

栈顶 到 栈底 数据从小到大，遇到比栈顶大的数就弹栈

数据： [2, 1, 3, 5, 4]

比如：

第一步： 2 入栈

第二步：1入栈

第三步：3入栈，大于栈顶1，1出栈； 又大于栈顶2，2出栈，栈内只有3

image-20210401103312684.png

依次类推：

最后栈内 只剩下 5 4

image-20210401105153905.png

2.单调递减栈：

栈顶 到 栈底 数据从大到小，遇到比栈顶小的数就弹栈

K 数题 单调栈解法

以时间复杂度O(n)从长度为n的数组中找出同时满足下面两个条件的所有元素：

（1）该元素比放在它左边的所有元素都大；

（2）该元素比放在它右边的所有元素都小

数据： [2, 1, 3, 5, 4] ，result 为 3

分析：

（1）单调递增数组肯定满足条件, 如[1, 2, 3, 4, 5]，也就是单调递减栈

（2）维护一个栈，仅仅是单调递减是不够的，元素入栈的时候只能保证比栈内的数据都大，但是不能保证比之前（已经出栈的）数据大

（3）需要维护一个最大值，来判断当前元素 左边是否有 比自己大的元素

步骤： 当前元素与 max 相比，只有比 max 大的 才可以入栈

（1） 2 入栈， max = 2， 数组为[2]

（2）1 小于 2，开始弹栈， 2 弹出， max = 2 ，数组为 []

（3）3 入栈， max = 3， 数组为[3]

（4）5 入栈， max = 5， 数组为[3，5]

（5）4 小于 5，开始弹栈， 5弹出，数组为 [3]

Jietu20210401-114909.jpg

时间复杂度：O(n)

（1）内嵌的 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)
                }
            }
        }
    }
    
    // 去除最后一个满足条件的数，因为右边没有元素
    if let last = res.last, last == nums.last {
        res.removeLast()
    }
  
    return res
}