给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
示例:
输入: 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
算法
swift
/**
暴力解法
外层循环数组，内层循环窗口k，找到最大值
时间复杂度为O(n*k)
空间复杂度为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
}
/**
双端队列
单调递减队列，保证队列头部始终是最大值
尾部插入数据，判断当前索引值 ？ 尾部索引值，小于：尾插；否则，移除尾部数据
判断队列内的元素个数是否超出窗口k， 当前索引 - 队列头部索引 ？k 超出，移除队列头部
参考题解：https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/
时间复杂度为O(n)
空间复杂度为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)
// 双端队列，单调递减，保证头部为最大值
var deque = [Int]()
var currentIndex = 0
for i in 0..<nums.count {
// 当前索引值 大于等于 队列尾部的值，移除尾部索引
while !deque.isEmpty && nums[i] >= nums[deque.last!] {
deque.removeLast()
}
deque.append(i)
// 队列头部的索引超出当前窗口，移除头部索引
while deque.first! <= i - k {
deque.removeFirst()
}
// 数组索引小于 k-1 的元素不需要保存记录
if i >= k - 1 {
results[currentIndex] = nums[deque.first!]
currentIndex += 1
}
}
return results
}
