LeetCode 239. 滑动窗口最大值 - 单调队列解法详解
一、问题理解
问题描述
给定一个整数数组 nums 和一个整数 k，滑动窗口从数组的最左侧移动到最右侧，每次只向右移动一位。请找出所有滑动窗口中的最大值，并返回这些最大值组成的数组。
示例
text
输入：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
二、核心思路：单调队列维护潜在最大值
暴力解法的局限性
对于每个窗口都重新遍历 k 个元素找最大值，时间复杂度为 O(nk)，效率极低。
单调队列优化思路
单调队列定义：使用双端队列（Deque）维护一个单调递减的队列，存储元素的索引。
队列特性：
队列中的索引对应的元素值从队首到队尾单调递减。
队首元素总是当前窗口的最大值。
维护操作：
入队：新元素入队时，从队尾开始移除所有小于等于它的元素，然后入队。
出队：检查队首元素是否还在当前窗口内，如果不在则移除。
获取最大值：窗口完全形成后，队首元素即为当前窗口最大值。
三、代码逐行解析
Java 解法
java
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
// 1. 结果数组：滑动窗口的个数为 n - k + 1
int[] ans = new int[n - k + 1];
// 2. 双端队列：存储元素索引，维护队列内元素值单调递减
Deque<Integer> q = new ArrayDeque<>();
// 3. 遍历数组的每个元素
for (int i = 0; i < n; i++) {
// 3.1 新元素从队尾入队，维护队列单调性
// 从队尾开始，移除所有小于等于当前元素的索引
// 因为这些元素不可能成为后续窗口的最大值
while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
q.removeLast();
}
// 将当前元素索引加入队尾
q.addLast(i);
// 3.2 移除窗口外的元素
// 计算当前窗口的左边界
int left = i - k + 1;
// 如果队首索引小于左边界，说明队首元素不在当前窗口内
if (q.getFirst() < left) {
q.removeFirst();
}
// 3.3 当窗口完全形成时，记录当前窗口最大值
// 当 left >= 0 时，窗口已包含 k 个元素
if (left >= 0) {
ans[left] = nums[q.getFirst()];
}
}
// 4. 返回结果
return ans;
}
}
Python 解法
python
from collections import deque
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
# 1. 边界处理
if n == 0 or k == 0:
return []
# 2. 初始化结果数组和双端队列
ans = [0] * (n - k + 1)
q = deque()
# 3. 遍历数组
for i in range(n):
# 3.1 维护队列单调性
# 从队尾开始，移除所有小于等于当前元素的索引
while q and nums[q[-1]] <= nums[i]:
q.pop()
# 将当前索引加入队尾
q.append(i)
# 3.2 移除窗口外的元素
# 计算当前窗口的左边界
left = i - k + 1
# 如果队首索引小于左边界，说明不在当前窗口内
if q[0] < left:
q.popleft()
# 3.3 记录结果（当窗口完全形成时）
if left >= 0:
ans[left] = nums[q[0]]
# 4. 返回结果
return ans
四、Java 与 Python 语法对比
1. 队列操作
操作 Java Python
创建双端队列 Deque<Integer> q = new ArrayDeque<>(); q = deque()
获取队尾元素 q.getLast() q[-1]
移除队尾元素 q.removeLast() q.pop()
获取队首元素 q.getFirst() q[0]
移除队首元素 q.removeFirst() q.popleft()
添加元素到队尾 q.addLast(i) q.append(i)
2. 数组/列表操作
操作 Java Python
创建数组 int[] ans = new int[n - k + 1]; ans = [0] * (n - k + 1)
获取数组长度 nums.length len(nums)
获取数组元素 nums[i] nums[i]
3. 循环与控制流
操作 Java Python
for 循环 for (int i = 0; i < n; i++) for i in range(n):
while 循环 while (!q.isEmpty() && ...) while q and ...:
五、实例演示
以测试用例 nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 为例，演示过程：
步骤 i nums[i] 队列操作（维护单调性后） 队列（索引，值） left 队首在窗口内？ ans[left]
1 0 1 空队列，直接加入0 [0(1)] -2 不判断 -
2 1 3 1(3) > 0(1)，移除0，加入1 [1(3)] -1 不判断 -
3 2 -1 队尾1(3) > -1，直接加入2 [1(3), 2(-1)] 0 是 (1>=0) ans[0]=3
4 3 -3 队尾2(-1) > -3，直接加入3 [1(3), 2(-1), 3(-3)] 1 是 (1>=1) ans[1]=3
5 4 5 依次移除3(-3), 2(-1), 1(3)，加入4 [4(5)] 2 是 (4>=2) ans[2]=5
6 5 3 队尾4(5) > 3，直接加入5 [4(5), 5(3)] 3 是 (4>=3) ans[3]=5
7 6 6 移除5(3), 4(5)，加入6 [6(6)] 4 是 (6>=4) ans[4]=6
8 7 7 移除6(6)，加入7 [7(7)] 5 是 (7>=5) ans[5]=7
最终结果：ans = [3, 3, 5, 5, 6, 7]
六、关键细节解析
1. 为什么队列存储索引而不是值？
索引可以判断元素是否在窗口内：通过比较索引和窗口左边界，可以知道元素是否已经滑出窗口。
值无法判断位置：如果只存储值，无法知道该值对应的元素是否还在当前窗口内。
2. 为什么入队时要移除小于等于当前元素的队尾元素？
假设队列尾部有元素 x，当前元素为 y，且 x <= y：
y 比 x 更大（或相等）且更靠右（索引更大）。
在后续窗口中，y 会比 x 更晚离开窗口。
因此，x 永远不可能成为后续窗口的最大值，可以安全移除。
3. 窗口何时完全形成？
当 i >= k - 1 时，left = i - k + 1 >= 0，此时窗口包含 k 个元素，可以记录最大值。
4. 为什么队首一定是当前窗口的最大值？
队列维护了从队首到队尾的单调递减性。
队首元素是当前窗口中最早加入队列且未被移除的元素。
通过入队时的筛选，队首元素一定大于队列中其他元素，且在当前窗口内。
七、复杂度分析
时间复杂度：O(n)
每个元素最多入队一次、出队一次。
每个元素的操作次数是常数级别。
总操作次数为 O(n)。
空间复杂度：O(k)
队列中最多同时存储 k 个元素（当数组单调递减时）。
结果数组 O(n-k+1) 不计入空间复杂度（属于输出要求）。
八、优化技巧与变体
1. 处理边界情况
python
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or k <= 0:
return []
n = len(nums)
if k == 1:
return nums
if k >= n:
return [max(nums)]
# 后续逻辑...
2. 使用数组模拟双端队列（优化空间）
python
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
if n == 0 or k == 0:
return []
# 使用列表模拟双端队列
q = [0] * n # 预分配空间
front, rear = 0, -1 # 队列的头部和尾部指针
ans = [0] * (n - k + 1)
for i in range(n):
# 维护队列单调性
while front <= rear and nums[q[rear]] <= nums[i]:
rear -= 1
rear += 1
q[rear] = i
# 移除窗口外的元素
if q[front] < i - k + 1:
front += 1
# 记录结果
if i >= k - 1:
ans[i - k + 1] = nums[q[front]]
return ans
3. 使用优先队列（堆）的解法
python
import heapq
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or k == 0:
return []
n = len(nums)
# 使用最大堆，存储（-值，索引）对，因为Python的heapq是最小堆
heap = []
result = []
for i in range(n):
# 将当前元素加入堆中
heapq.heappush(heap, (-nums[i], i))
# 当窗口完全形成时
if i >= k - 1:
# 移除堆顶不在窗口内的元素
while heap and heap[0][1] <= i - k:
heapq.heappop(heap)
# 堆顶元素就是当前窗口的最大值
result.append(-heap[0][0])
return result
复杂度分析：
时间复杂度：O(n log n)，每个元素入堆出堆需要 O(log n)
空间复杂度：O(n)
缺点：比单调队列解法慢，但逻辑更简单。
九、常用函数积累
Java 常用函数
java
// 双端队列操作
Deque<Integer> deque = new ArrayDeque<>();
deque.addLast(element); // 添加到队尾
deque.removeLast(); // 移除队尾
deque.getLast(); // 获取队尾
deque.addFirst(element); // 添加到队首
deque.removeFirst(); // 移除队首
deque.getFirst(); // 获取队首
deque.isEmpty(); // 判断队列是否为空
deque.size(); // 获取队列大小
// 数组操作
int[] arr = new int[n];
int length = arr.length; // 数组长度
Arrays.fill(arr, value); // 填充数组
Python 常用函数
python
from collections import deque
# 双端队列操作
q = deque()
q.append(element) # 添加到队尾
q.pop() # 移除队尾
q[-1] # 获取队尾
q.appendleft(element) # 添加到队首
q.popleft() # 移除队首
q[0] # 获取队首
len(q) # 获取队列大小
bool(q) # 判断队列是否非空
# 列表操作
arr = [0] * n
len(arr) # 列表长度
max(arr) # 获取最大值
min(arr) # 获取最小值
十、总结
核心要点
单调队列是关键：维护一个单调递减的队列，队首元素始终是当前窗口的最大值。
索引存储很重要：存储索引而非值，可以方便地判断元素是否在窗口内。
时间复杂度优化：从暴力解法的 O(nk) 优化到 O(n)。
面试常见问题
为什么使用单调队列而不是优先队列？
单调队列的均摊时间复杂度是 O(1)，而优先队列是 O(log n)。
单调队列更适合滑动窗口问题，因为元素是按顺序加入和移除的。
如何处理数组中有重复元素的情况？
算法天然支持重复元素，因为入队时移除的是小于等于当前元素的元素。
如果有多个相同的最大值，队列中会保留最右侧的那个（索引最大的）。
如果 k 很大，接近 n 怎么办？
算法仍然有效，队列大小最多为 k，空间复杂度 O(k)。
当 k >= n 时，只需要返回整个数组的最大值。
最坏情况下的时间复杂度？
每个元素最多入队一次、出队一次，所以是 O(n)。
如果数组是单调递增的，队列会怎样？
队列中最多只会有一个元素，因为每个新元素都会移除之前的所有元素。
扩展思考
类似问题：
滑动窗口最小值（只需将单调递减改为单调递增）
滑动窗口的中位数（需要更复杂的数据结构）
滑动窗口的平均值（更简单，只需维护窗口和）
变体问题：
限制大小的队列最大值（队列有最大容量，需要支持push和pop）
二维滑动窗口最大值（更复杂，需要结合单调队列和动态规划）
实际应用：
股票价格分析（寻找一段时间内的最高价）
网络流量监控（统计固定时间窗口内的最大流量）
图像处理（滑动窗口滤波器）
掌握单调队列的解法，不仅能够解决滑动窗口最大值问题，还能够解决一系列类似的区间最值问题，是面试中非常重要的算法技巧。
————————————————
版权声明：本文为CSDN博主「好学且牛逼的马」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/King_model/article/details/154684394
