給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。
返回滑動(dòng)窗口中的最大值。
進(jìn)階：
你能在線性時(shí)間復(fù)雜度內(nèi)解決此題嗎？
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動(dòng)窗口的位置 最大值
[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)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
算法
swift
/**
暴力解法
外層循環(huán)數(shù)組，內(nèi)層循環(huán)窗口k，找到最大值
時(shí)間復(fù)雜度為O(n*k)
空間復(fù)雜度為O(1)
提交LeetCode超時(shí)
*/
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
}
/**
雙端隊(duì)列
單調(diào)遞減隊(duì)列，保證隊(duì)列頭部始終是最大值
尾部插入數(shù)據(jù)，判斷當(dāng)前索引值 ？ 尾部索引值，小于：尾插；否則，移除尾部數(shù)據(jù)
判斷隊(duì)列內(nèi)的元素個(gè)數(shù)是否超出窗口k， 當(dāng)前索引 - 隊(duì)列頭部索引 ？k 超出，移除隊(duì)列頭部
參考題解：https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/
時(shí)間復(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)
// 雙端隊(duì)列，單調(diào)遞減，保證頭部為最大值
var deque = [Int]()
var currentIndex = 0
for i in 0..<nums.count {
// 當(dāng)前索引值 大于等于 隊(duì)列尾部的值，移除尾部索引
while !deque.isEmpty && nums[i] >= nums[deque.last!] {
deque.removeLast()
}
deque.append(i)
// 隊(duì)列頭部的索引超出當(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
}
