給定一個數(shù)組 nums庶香，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口內(nèi)的 k 個數(shù)字简识「弦矗滑動窗口每次只向右移動一位。
返回滑動窗口中的最大值七扰。
進(jìn)階：
你能在線性時間復(fù)雜度內(nèi)解決此題嗎奢赂？
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sliding-window-maximum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)戳寸，非商業(yè)轉(zhuǎn)載請注明出處呈驶。
算法
swift
/**
暴力解法
外層循環(huán)數(shù)組，內(nèi)層循環(huán)窗口k疫鹊，找到最大值
時間復(fù)雜度為O(n*k)
空間復(fù)雜度為O(1)
提交LeetCode超時
*/
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
// 過濾邊界
guard nums.count > 0 else {
return []
}
var results = [Int]()
for i in 0..<nums.count-k+1 {
var maxValue = nums[i]
for j in 1..<k {
maxValue = max(maxValue, nums[i+j])
}
results.append(maxValue)
}
return results
}
/**
雙端隊列
單調(diào)遞減隊列袖瞻，保證隊列頭部始終是最大值
尾部插入數(shù)據(jù)，判斷當(dāng)前索引值 拆吆？ 尾部索引值聋迎，小于：尾插；否則枣耀，移除尾部數(shù)據(jù)
判斷隊列內(nèi)的元素個數(shù)是否超出窗口k霉晕， 當(dāng)前索引 - 隊列頭部索引 ？k 超出，移除隊列頭部
參考題解：https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/
時間復(fù)雜度為O(n)
空間復(fù)雜度為O(n)
*/
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
// 過濾邊界
guard nums.count > 0 else {
return []
}
var results = [Int](repeating: 0, count: nums.count-k+1)
// 雙端隊列牺堰，單調(diào)遞減拄轻，保證頭部為最大值
var deque = [Int]()
var currentIndex = 0
for i in 0..<nums.count {
// 當(dāng)前索引值 大于等于 隊列尾部的值，移除尾部索引
while !deque.isEmpty && nums[i] >= nums[deque.last!] {
deque.removeLast()
}
deque.append(i)
// 隊列頭部的索引超出當(dāng)前窗口伟葫，移除頭部索引
while deque.first! <= i - k {
deque.removeFirst()
}
// 數(shù)組索引小于 k-1 的元素不需要保存記錄
if i >= k - 1 {
results[currentIndex] = nums[deque.first!]
currentIndex += 1
}
}
return results
}
