力扣热门100题之滑动窗口最大值【困难】

**力扣热门100题之滑动窗口最大值**

**难度:**困难**描述:**

给定一个整数数组 `nums` 和一个整数 `k`。请设计一个算法,在每个时间步长上输出当前窗口内的最大值。

**示例1:**

输入:`nums = [1,3,-1,-3,5,3,6,7], k =3`

输出:`[3,3,3,3,7,7,7,7]`

**示例2:**

输入:`nums = [1], k =1`

输出:`[1]`

**思路:**

本题要求我们设计一个算法,在每个时间步长上输出当前窗口内的最大值。我们可以使用滑动窗口技术来解决这个问题。

首先,我们需要维护一个双端队列 `deque` 来存储当前窗口内的元素。我们将使用两个指针 `left` 和 `right` 来表示当前窗口的左边界和右边界。

当新元素进入窗口时,我们需要更新 `right` 指针并将新元素添加到双端队列中。如果新元素大于双端队列中的最大值,我们需要将最大值弹出并更新 `left` 指针。

当旧元素离开窗口时,我们需要更新 `left` 指针并将最小值弹出。这样可以保证当前窗口内的最大值始终是正确的。

**代码:**

from collections import dequeclass Solution:
 def maxSlidingWindow(self, nums, k):
 """
 :type nums: List[int]
 :type k: int :rtype: List[int]
 """
 n = len(nums)
 if n ==0 or k ==0:
 return []
 # Initialize the deque and pointers dq = deque()
 left, right =0,0 # Process the first window while right < k:
 while dq and nums[dq[-1]] < nums[right]:
 dq.pop()
 dq.append(right)
 right +=1 # Process the rest of the windows result = []
 for i in range(n - k +1):
 result.append(nums[dq[0]])
 # Update the deque and pointers while dq and dq[0] < i:
 dq.popleft()
 while dq and nums[dq[-1]] < nums[right]:
 dq.pop()
 dq.append(right)
 right +=1 return result# Test casessolution = Solution()

print(solution.maxSlidingWindow([1,3,-1,-3,5,3,6,7],3)) # Output: [3,3,3,3,7,7,7,7]
print(solution.maxSlidingWindow([1],1)) # Output: [1]

**注释:**

* 我们使用双端队列 `deque` 来存储当前窗口内的元素。这样可以保证我们始终能找到当前窗口内的最大值。
* 我们使用两个指针 `left` 和 `right` 来表示当前窗口的左边界和右边界。
* 当新元素进入窗口时，我们需要更新 `right` 指针并将新元素添加到双端队列中。如果新元素大于双端队列中的最大值,我们需要将最大值弹出并更新 `left` 指针。
* 当旧元素离开窗口时，我们需要更新 `left` 指针并将最小值弹出。这样可以保证当前窗口内的最大值始终是正确的。

**时间复杂度:**

* 初始化双端队列和指针的时间复杂度为 O(k)。
* 处理每个窗口的时间复杂度为 O(1)。
* 总体时间复杂度为 O(nk)。

**空间复杂度:**

* 使用双端队列存储当前窗口内的元素所需的空间复杂度为 O(k)。
* 总体空间复杂度为 O(n + k)。