难度: Hard
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：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
示例 2：
输入：nums = [1], k = 1 输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length运行时间: 156 ms
内存: 0.0 MB
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or not k:
return []
queue, output = collections.deque([]), []
for i in range(len(nums)):
#queue存index，index代表的数字是递减的
while queue and nums[i]>nums[queue[-1]]:
queue.pop()
queue.append(i)
#此时开始有max_window存在；queue[0]永远是当前窗口里最大值
if i>=k-1:
output.append(nums[queue[0]])
#i代表window上边界
if i+1-k==queue[0]:
queue.popleft()
return output
该题解使用双端队列实现了单调队列，维护了一个队列存储窗口内的元素下标。通过控制队列的进出，保证队首下标对应的元素始终是当前窗口内的最大值。在窗口滑动的过程中，不断将队尾元素与当前元素比较，将小于当前元素的下标弹出，并将当前元素下标加入队尾。当窗口形成后，每次将队首元素对应的值加入输出数组中。同时，当窗口滑出某个下标时，若该下标是队首元素，则将其从队列中弹出。
时间复杂度: O(n)
空间复杂度: O(k)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or not k:
return []
queue, output = collections.deque([]), []
for i in range(len(nums)):
# 维护单调递减队列，队列存储元素下标
while queue and nums[i] > nums[queue[-1]]:
queue.pop()
queue.append(i)
# 当窗口形成后，将队首元素对应的值加入输出数组
if i >= k - 1:
output.append(nums[queue[0]])
# 当窗口滑出某个下标时，若该下标是队首元素，则将其弹出
if i - k + 1 == queue[0]:
queue.popleft()
return output
双端队列（deque）允许我们从两端高效地添加和删除元素，这是实现单调队列时非常重要的功能。使用双端队列，可以在O(1)时间内从队尾添加新的元素，以及从队首移除旧的元素。如果使用数组，尽管可以在末尾添加元素，但从数组的开始位置删除元素的效率较低，通常是O(n)；而链表虽然可以在两端高效地添加和删除元素，但在实际操作中，相比于双端队列，其节点的动态分配和额外的指针操作可能使得性能稍逊一筹。因此，双端队列是实现此类功能的最佳选择。
存储元素的下标而不是值有几个重要的优势。首先，通过下标可以直接访问元素的值，并且可以检查这些下标是否还在滑动窗口的范围内。这种方法特别有助于在窗口滑动时快速确定哪些元素应该从队列中移除：如果队首的下标不再位于当前窗口内，我们可以将其快速弹出。此外，这也使得在数组中移动窗口时，能够保持与原始数据的直接联系，方便操作和理解。
为了确保队列的单调递减性，每当新的元素准备加入队列时，算法会从队列的尾部开始，逐一比较已有的元素。如果队尾元素对应的值小于当前元素的值，则这些队尾元素会被连续弹出，直到遇到一个值大于或等于当前元素的值或队列为空为止。这样可以保证队列中的元素是按照从大到小的顺序排列的，队首元素始终是当前窗口的最大值。这个过程确保了每次插入操作后队列的单调递减性。
当窗口向右移动时，窗口的起始索引也随之增加。如果队列的队首元素的下标小于当前窗口的起始索引，那么这个元素已不再属于当前窗口范围内。在这种情况下，我们需要从队列的队首移除这个下标。这样做是必要的，因为只有在队首的下标仍然位于窗口内时，我们才能保证队首元素是窗口中的最大值。这确保了输出数组中始终是每个窗口的最大值。