Swift 单调递减栈解决 K数 问题
2021-04-01 本文已影响0人
overla5
什么是单调栈?
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]
时间复杂度: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
}