题目描述
给你一个整数数组 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
最终结果为：
[3,3,5,5,6,7]
解题思路
这道题最直接的想法是：
-
每次窗口移动后，都重新遍历当前窗口的
k个元素 -
找出其中最大值
这种做法当然可以做出来，但时间复杂度是：
O(n * k)
如果数组很长、窗口也很大，效率会很差。
所以这道题的关键就在于：
窗口每次只移动一格，如何快速知道新窗口的最大值，而不是每次都重新遍历。
这正是单调队列最擅长解决的问题。
为什么要用单调队列
我们希望维护一个结构，使得它满足两件事：
-
能快速拿到当前窗口最大值
-
当窗口右移时，能快速删除过期元素，并加入新元素
如果我们能让队列里的元素始终保持“从大到小”的顺序，那么：
-
队头就是当前窗口最大值
-
新元素加入时，可以把后面比它小的元素全部删掉
-
因为这些更小的元素即使留着，也永远不可能成为后续窗口的最大值
这就是单调队列的核心思想。
你的代码思路
你给出的代码如下：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for(int i = 0; i < k; i++) {
while(!deque.isEmpty() && deque.peekLast() < nums[i])
deque.removeLast();
deque.addLast(nums[i]);
}
res[0] = deque.peekFirst();
for(int i = k; i < nums.length; i++) {
if(deque.peekFirst() == nums[i - k])
deque.removeFirst();
while(!deque.isEmpty() && deque.peekLast() < nums[i])
deque.removeLast();
deque.addLast(nums[i]);
res[i - k + 1] = deque.peekFirst();
}
return res;
}
}
这份代码维护的是一个从大到小排列的双端队列。
注意你这里队列里存的不是下标，而是元素值本身。 这也是一种可以通过的写法，只不过更常见的标准写法会存下标。
单调队列里存的是什么
在你的代码里：
Deque<Integer> deque = new LinkedList<>();
这个队列保存的是当前窗口中“有资格成为最大值”的元素，并且保持从大到小排列。
例如当前窗口里的元素是：
[1, 3, -1]
处理完之后，队列大致会变成：
[3, -1]
为什么 1 不在了？
因为当 3 进入队列时，1 比它小，而且 1 又在 3 前面。 只要 3 还在窗口中，1 永远不可能成为最大值，所以可以直接删掉。
为什么队头一定是最大值
因为我们始终保证队列中的元素从大到小排列：
队头 >= 队尾前一个 >= 队尾
这样队头自然就是当前窗口中的最大值。
所以每次窗口形成之后，直接取：
deque.peekFirst()
就是答案。
维护单调性的核心操作
每次加入新元素 nums[i] 时，都要做这一步：
while(!deque.isEmpty() && deque.peekLast() < nums[i])
deque.removeLast();
deque.addLast(nums[i]);
这表示：
-
如果队尾元素比当前新元素小
-
那么它就不可能在未来成为最大值
-
因为它既比新元素小，又比新元素更早离开窗口
所以直接从队尾删除。
一直删到：
-
队列为空
-
或者队尾元素大于等于当前元素
然后再把当前元素加到队尾。
这就能保证整个队列始终单调递减。
为什么窗口左边滑出去时要判断队头
窗口每向右滑动一次，就会有一个旧元素离开窗口：
nums[i - k]
如果这个离开的元素刚好等于队头，那么说明当前窗口的最大值已经过期了，就要把它删掉：
if(deque.peekFirst() == nums[i - k])
deque.removeFirst();
如果离开的元素不是队头，那就说明它本来就不是当前窗口的最大值，或者早就已经在队列维护过程中被淘汰掉了，不需要额外处理。
代码解析
1. 边界判断
if(nums.length == 0 || k == 0) return new int[0];
如果数组为空，或者窗口大小为 0，直接返回空数组。
2. 定义单调队列和结果数组
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
-
deque：维护当前窗口中的候选最大值 -
res：保存每个窗口的最大值
结果数组长度为什么是：
nums.length - k + 1
因为长度为 n 的数组中，大小为 k 的窗口一共可以滑出这么多个位置。
3. 先处理第一个窗口
for(int i = 0; i < k; i++) {
while(!deque.isEmpty() && deque.peekLast() < nums[i])
deque.removeLast();
deque.addLast(nums[i]);
}
res[0] = deque.peekFirst();
这一步先把前 k 个元素放进队列，并维护单调递减。
处理完之后，队头就是第一个窗口的最大值。
4. 开始滑动窗口
for(int i = k; i < nums.length; i++) {
从第 k 个元素开始，每次加入一个新元素，同时滑走一个旧元素。
5. 删除过期元素
if(deque.peekFirst() == nums[i - k])
deque.removeFirst();
nums[i - k] 就是当前窗口左边刚刚滑出去的元素。
如果它恰好等于队头，说明原来的最大值已经过期了，需要删掉。
6. 加入新元素，并维护单调性
while(!deque.isEmpty() && deque.peekLast() < nums[i])
deque.removeLast();
deque.addLast(nums[i]);
把比新元素小的队尾元素全部删掉，再把新元素加入队尾。
7. 记录当前窗口最大值
res[i - k + 1] = deque.peekFirst();
队头始终是当前窗口最大值。
示例推演
我们用示例：
nums = [1,3,-1,-3,5,3,6,7], k = 3
来简单模拟一下。
第一个窗口 [1,3,-1]
依次加入：
-
加入
1，队列：[1] -
加入
3，1 < 3，删掉1，队列变成：[3] -
加入
-1，队列变成：[3,-1]
当前窗口最大值：
3
窗口右移，变成 [3,-1,-3]
滑出去的是 1：
-
队头是
3，不是1，不用删
加入 -3：
-
队尾
-1 < -3不成立，直接加入
队列：
[3,-1,-3]
当前最大值还是：
3
窗口右移，变成 [-1,-3,5]
滑出去的是 3：
-
队头正好是
3，删掉
加入 5：
-
-3 < 5，删 -
-1 < 5，删 -
最后加入
5
队列：
[5]
当前最大值：
5
后面过程也是同样的道理。
为什么这题能做到 O(n)
很多同学第一次看单调队列时，会担心：
里面既有
for，又有while，是不是会退化成O(n^2)？
其实不会。
关键在于：
-
每个元素最多只会入队一次
-
每个元素最多只会被从队尾弹出一次
-
每个元素最多只会被从队头弹出一次
所以整体来看，每个元素参与队列操作的次数是有限的。
因此总时间复杂度仍然是：
O(n)
这份代码和“存下标”的标准写法有什么区别
更常见的标准写法，队列里存的是下标，而不是值。
这样做的好处是：
-
可以更准确地判断元素是否过期
-
即使有重复值，也不会依赖值比较来删除窗口左边元素
而你这份代码存的是值本身，在这道题里也是能工作的，因为：
-
维护的是单调递减队列
-
过期时只要判断队头是否等于滑出的值即可
不过从模板化和通用性来说，面试中更推荐掌握“存下标”的写法。
但作为理解单调队列原理，这份代码其实非常直观。
复杂度分析
设数组长度为 n。
时间复杂度
O(n)
每个元素最多进队一次、出队一次。
空间复杂度
O(k)
队列中最多存放当前窗口相关的元素，数量不会超过窗口大小。
总结
用一个单调递减队列，维护当前窗口内可能成为最大值的元素。
这样就能做到：
-
队头始终是当前窗口最大值
-
新元素加入时，把所有比它小的队尾元素删掉
-
窗口滑动时，如果队头元素过期，就把它删除
-
整个过程每个元素只处理有限次，所以复杂度是
O(n)
你可以把这题总结成一句话：
滑动窗口最大值 = 单调队列维护窗口最大候选人，队头永远是答案。
这是一道非常经典的单调队列题，也是这个数据结构最有代表性的一道题，值得彻底掌握。
