239. 滑动窗口的最大值（Hard）
题目描述
给定一个数组 nums 和滑动窗口的大小 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
题解
通过维持一个单调的队列去实现
单调队列的实现方式是通过 双端队列 的数据结构
Python代码示例
# 单指针写法
import collections
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
deque = collections.deque()
ans = []
for i in range(len(nums)):
# ----- 维持递减单调队列 ----
while deque and nums[i] > deque[-1]: # 右移准备，维持单调队列
deque.pop()
deque.append(nums[i])
# ----- 滑动窗口操作 ----
if i - k >= 0 and nums[i - k] == deque[0]: # 左移时正好移出最大值
deque.popleft()
# ------ 状态记录 ------
if i - k + 1 >= 0: # 存在长度为k的滑动窗口
ans.append(deque[0])
return ans
# 双指针写法
import collections
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
deque = collections.deque()
ans = []
for i, j in zip(range(-k + 1, len(nums) - k + 1), range(len(nums))): # i 的位置是 j - k + 1
while deque and nums[j] > deque[-1]:
deque.pop()
deque.append(nums[j]) # 右移窗口
if i > 0 and deque[0] == nums[i - 1]: # 左移窗口
deque.popleft()
if i >= 0: # 加入节点
ans.append(deque[0])
return ans
Go 示例
func maxSlidingWindow(nums []int, k int) []int {
deque := make([]int, 0)
i, j := -k + 1, 0
n := len(nums)
ans := make([]int, 0)
for j < n {
for len(deque) > 0 && nums[j] > deque[len(deque) - 1] { // nums[j] > deque[len(deque) - 1] 很容易错！！ 这里一定是没有等号的，如 [-7,-8,7,5,7,1,6,0] 这个样例
deque = deque[:len(deque) - 1]
}
deque = append(deque, nums[j])
if i > 0 && deque[0] == nums[i - 1] {
deque = deque[1:]
}
// 添加结果的这一步必须放在左移和右移之后，不然会出错，比如 [1, -1] 这个测试样例
if i >=0 {
ans = append(ans, deque[0])
}
i++
j++
}
return ans
}