239. 滑动窗口最大值

**滑动窗口最大值**

在计算机科学中，滑动窗口是一种常见的算法设计模式。它通常用于处理序列数据，如时间序列、图像或文本等。在本文中，我们将讨论一个具体的问题：给定一个整数数组和一个滑动窗口大小，求出每个子数组中的最大值。

**问题描述**

假设我们有一个整数数组 `nums` 和一个滑动窗口大小 `k`。我们的任务是设计一个算法，能够在不额外使用额外空间的情况下，对于每个子数组（长度为 `k` 的连续元素），计算出最大值。

**解决方案**

我们可以使用双端队列（Deque）来实现这个问题。Deque 是一种特殊的线性表，它允许从两端添加或删除元素。在本例中，我们将使用 Deque 来存储当前窗口内的元素。

from collections import dequedef maxSlidingWindow(nums, k):
 """
 滑动窗口最大值 Args:
 nums (list): 整数数组 k (int): 滑动窗口大小 Returns:
 list: 每个子数组中的最大值 """
 # 初始化结果列表和双端队列 result = []
 dq = deque()
 # 遍历数组 for i, num in enumerate(nums):
 # 当前元素进入窗口时，移除不再在窗口内的元素 while dq and dq[0] < i - k +1:
 dq.popleft()
 # 移除小于当前元素的元素 while dq and nums[dq[-1]] < num:
 dq.pop()
 # 将当前元素添加到双端队列 dq.append(i)
 # 当前窗口完整时，添加最大值到结果列表 if i >= k -1:
 result.append(nums[dq[0]])
 return result

**示例**

nums = [1,3, -1, -3,5,3,6,7]
k =3print(maxSlidingWindow(nums, k)) # 输出：[3,3,5,5,6,7]

**注释**

* 我们使用 Deque 来存储当前窗口内的元素。这允许我们在 O(1) 时间复杂度下添加或删除元素。
* 当前元素进入窗口时，我们移除不再在窗口内的元素。这确保了我们的双端队列始终包含当前窗口内的最大值。
* 我们使用 `while` 循环来移除小于当前元素的元素。这保证了我们的双端队列始终包含当前窗口内的最大值。
* 当前窗口完整时，我们添加最大值到结果列表。这确保了我们得到每个子数组中的最大值。

**时间复杂度**

* 初始化结果列表和双端队列：O(k)
* 遍历数组：O(n)
* 移除不再在窗口内的元素：O(1)
* 移除小于当前元素的元素：O(1)
* 将当前元素添加到双端队列：O(1)

总时间复杂度为 O(n)。

**空间复杂度**

* 初始化结果列表和双端队列：O(k)
* 双端队列中存储的元素数量不超过 k总空间复杂度为 O(k)。