题目描述

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

问题分析

需要在一个大小为 k 的滑动窗口内找到当前窗口内的最大值。滑动窗口从数组的最左侧开始，每次向右移动一位。最简单的方式是对于每个窗口都遍历其内部元素找出最大值，但这种方法的时间复杂度较高

优化思路

可以利用双端队列（Deque）来优化这个过程，使得在每次移动滑动窗口时都能在 O(1) 的时间复杂度内得到当前窗口的最大值。

具体步骤

1、我们维护一个双端队列 deque，其中存储数组元素的索引，并且保证队列中存储的索引对应的数组值是单调递减的。这样，队列的第一个元素总是当前窗口的最大值的索引。
2、在滑动窗口向右移动一位时，首先检查队列的头部元素是否已经不在当前窗口内（即 deque[0] 小于窗口的左边界），如果是，则将其从队列中移除。
3、然后，将当前遍历到的元素的索引加入队列尾部。在加入之前，移除队列尾部那些比当前元素小的所有元素，因为它们不可能成为后续窗口中的最大值。
4、当遍历到的索引大于或等于 k-1 时（即窗口已经形成），将当前窗口的最大值（即 deque[0] 对应的元素）加入结果集中。

python">
```python
from collections import dequedef maxSlidingWindow(nums, k):if not nums:return []deque_window = deque()max_values = []for i in range(len(nums)):# 移除窗口外的元素if deque_window and deque_window[0] < i - k + 1:deque_window.popleft()# 移除所有小于当前元素的元素while deque_window and nums[deque_window[-1]] < nums[i]:deque_window.pop()# 添加当前元素的索引deque_window.append(i)# 当前窗口形成时，将最大值加入结果集if i >= k - 1:max_values.append(nums[deque_window[0]])return max_values

或者自定义单调栈

python">from collections import dequeclass MyQueue:def __init__(self):self.queue = deque()def pop(self, value):if self.queue and value == self.queue[0]:self.queue.popleft()def push(self, value):while self.queue and value > self.queue[-1]:self.queue.pop()self.queue.append(value)def front(self):return self.queue[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:que = MyQueue()res = []# 先将前k的元素导入单调递减队列for i in range(k):que.push(nums[i])res.append(que.front())# 移动窗口for i in range(k, len(nums)):que.pop(nums[i - k])que.push(nums[i])res.append(que.front())return res