#239
困难
中频
单调队列滑动窗口最大值
这是一道围绕数组、滑动窗口展开的高频练习。建议先掌握「单调队列」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
滑动窗口
题目分析
给你一个数组和窗口大小 k。
窗口从左到右滑动，每次向右移动一格，要求返回每个窗口中的最大值。
一句话概括：
窗口在移动时，要持续维护一个能快速给出当前最大值的结构。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用单调递减队列维护窗口候选最大值，队首始终是当前窗口最大元素下标。
推荐代码
推荐解法：单调队列
时间复杂度： O(n)
空间复杂度： O(k)
核心思路： 用单调递减队列维护窗口候选最大值，队首始终是当前窗口最大元素下标。
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用单调队列，让窗口最大值始终保持在队首。
核心过程
- 队列里存下标，并保持对应值单调递减。
- 加入新元素时，把队尾所有更小元素弹掉。
- 窗口滑动时，若队首下标过期就弹出。
- 窗口长度达到 k 后，队首对应值就是当前最大值。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(k)。
面试补一句：单调队列最重要的作用，是提前淘汰不可能成为答案的元素。
核心思路
滑动窗口最大值的重点不是“窗口会动”，而是“怎样在窗口滑动时还快速知道最大值”。单调队列通过把不可能成为答案的元素提前淘汰，保住了 O(1) 取最大值。
步骤讲解
1
维护队列单调递减
加入新元素前，先把队尾所有小于等于它的元素弹出，再把当前下标入队。
为什么这样做：这些更小元素只会更早过期，永远不可能再成为窗口最大值。
对应代码提示：while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) deque.pollLast();
2
滑窗时移除过期下标
如果队首下标已经滑出窗口左边界，就把它弹出。
为什么这样做：窗口最大值只能来自当前窗口内部。
对应代码提示：if (deque.peekFirst() <= i - k) deque.pollFirst();
3
窗口形成后读取队首
当窗口长度达到 k，队首下标对应的值就是当前窗口最大值。
为什么这样做：单调递减性质保证队首始终最大且仍在窗口内。
对应代码提示：answer[idx++] = nums[deque.peekFirst()];
易错点
队列里存值不存下标
这样就无法判断元素是否已经滑出窗口。
正确理解：队列必须存下标，值通过下标回查。
只在窗口形成后才维护单调性
会让队列状态混乱，无法保证队首总是最大值。
正确理解：每次加入新元素前都先清理队尾。
没先弹出过期元素就读答案
队首可能已经不在当前窗口里，答案会偏大。
正确理解：每轮先删过期，再在窗口形成后读队首。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(k)
比其他方案更好在哪里：比优先队列更快，避免了堆中懒删除带来的额外
log k 开销。适用判断：滑动窗口题只要问区间最大/最小值，优先考虑单调队列。
额外提醒
- 队列里的元素不一定都可能成为答案，但队首一定是当前答案。
其他语言 / 其他解法
分块+预处理
算法思路待补充
分块+预处理
算法思路待补充
时间复杂度：O(?)
空间复杂度：O(?)
一句话思路：算法思路待补充
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] prefixMax = new int[n];
int[] suffixMax = new int[n];
for (int i = 0; i < n; ++i) {
if (i % k == 0) {
prefixMax[i] = nums[i];
}
else {
prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
}
}
for (int i = n - 1; i >= 0; --i) {
if (i == n - 1 || (i + 1) % k == 0) {
suffixMax[i] = nums[i];
} else {
suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
}
}
int[] ans = new int[n - k + 1];
for (int i = 0; i <= n - k; ++i) {
ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
}
return ans;
}
}优先队列
算法思路待补充
优先队列
算法思路待补充
时间复杂度：O(?)
空间复杂度：O(?)
一句话思路：算法思路待补充
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}动画演示
如果你还没完全看懂，可以展开动画演示。
单调队列动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
单调队列动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
分块+预处理动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
分块+预处理动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
优先队列动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
优先队列动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。