第14篇-队列与单调队列-解决窗口最值问题的关键结构

概述：为什么学完栈之后要学队列

上一篇我们讲了栈。
栈的特点是：

后进先出

也就是最后放进去的元素最先被取出来。

而这一篇要讲的队列，正好是另一种非常基础的数据结构：

先进先出

也就是先放进去的元素先被取出来。

队列在算法题里经常出现在下面这些场景：

• 按顺序处理任务
• 模拟排队过程
• BFS 广度优先搜索
• 层序遍历二叉树
• 滑动窗口中的元素维护
• 单调队列解决窗口最大值、最小值问题

如果说栈适合处理“最近的未处理元素”，那么队列更适合处理：

最早进入、最早应该被处理的元素。

这篇文章会从普通队列讲起，再过渡到双端队列，最后重点讲单调队列。

你需要掌握下面几件事：

学完这篇，你应该能理解队列的先进先出思想，并掌握用单调队列在 O(n) 时间内解决窗口最值问题。

核心概念：队列到底是什么

队列是一种遵循 先进先出 规则的数据结构。

First In First Out

可以把它想象成排队买票：

队头 队尾
[1] -> [2] -> [3] -> [4] -> [5]
先来的人先被服务 后来的人排在后面

常见操作如下：

在 Java 中，算法题里常用 Queue 或 Deque 来表示队列。

普通队列写法：

import java.util.ArrayDeque;
import java.util.Queue;

Queue<Integer> queue = new ArrayDeque<>();

queue.offer(1);
queue.offer(2);
queue.offer(3);

int first = queue.peek(); // 1
int x = queue.poll(); // 1

如果需要同时操作队头和队尾，就使用 Deque。

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> deque = new ArrayDeque<>();

deque.offerLast(1); // 队尾加入
deque.offerLast(2);
deque.pollFirst(); // 队头弹出

队列强调处理顺序，谁先进入，谁就先被处理。

队列与栈的区别

栈和队列都可以存放一组元素，但它们的取出顺序完全不同。

看一个简单例子。

如果依次放入：

1, 2, 3

栈的取出顺序是：

3, 2, 1

队列的取出顺序是：

1, 2, 3

所以选择栈还是队列，关键要看题目需要的处理顺序：

• 如果要处理最近加入的元素，优先想栈
• 如果要处理最早加入的元素，优先想队列

普通队列的典型应用：BFS

队列最典型的应用是 BFS，也就是广度优先搜索。

BFS 的特点是：

先访问距离近的节点，再访问距离远的节点。

这种“按层扩展”的过程天然适合用队列。

比如从节点 A 出发：

A
/ | \\
B C D
/ |
E F

BFS 的访问顺序通常是：

A -> B -> C -> D -> E -> F

过程可以理解为：

BFS 通用模板

import java.util.ArrayDeque;
import java.util.Queue;

Queue<Integer> queue = new ArrayDeque<>();
boolean[] visited = new boolean[n];

queue.offer(start);
visited[start] = true;

while (!queue.isEmpty()) {
int cur = queue.poll();

for (int next : graph[cur]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}

为什么 BFS 要用队列

队列能保证：

先进入队列的节点先被处理。

在 BFS 中，先进入队列的节点通常距离起点更近。
所以队列可以自然维持“按层扩展”的顺序。

这也是 BFS 能解决最短步数问题的基础。

后面的 BFS 专题会展开讲，这里先记住队列和 BFS 的关系即可。

双端队列：Deque 为什么重要

普通队列只能从队尾加入、从队头删除。

但有些题目中，我们既需要操作队头，也需要操作队尾。
这时就需要双端队列。

Deque 的全称是：

Double Ended Queue

也就是两端都能操作的队列。

常用方法如下：

示例代码：

Deque<Integer> deque = new ArrayDeque<>();

deque.offerLast(1); // [1]
deque.offerLast(2); // [1, 2]
deque.offerFirst(0); // [0, 1, 2]

int a = deque.peekFirst(); // 0
int b = deque.peekLast(); // 2

deque.pollFirst(); // [1, 2]
deque.pollLast(); // [1]

双端队列是单调队列的基础。
因为单调队列既要从队尾删除不合格元素，也要从队头删除过期元素。

当题目需要同时维护队头和队尾时，优先考虑双端队列。

进阶概念：什么是单调队列

单调队列是在普通队列基础上增加了一个要求：

队列中的元素保持单调递增或单调递减。

常见有两类：

• 单调递减队列：队头到队尾的值越来越小
• 单调递增队列：队头到队尾的值越来越大

单调队列最经典的用途是：

在滑动窗口中快速得到最大值或最小值。

比如数组：

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

窗口长度为 3，每次向右滑动一格：

[1, 3, -1] 最大值 3
[3, -1, -3] 最大值 3
[-1, -3, 5] 最大值 5
[-3, 5, 3] 最大值 5
[5, 3, 6] 最大值 6
[3, 6, 7] 最大值 7

输出：

[3, 3, 5, 5, 6, 7]

如果每个窗口都暴力扫描一次，时间复杂度是：

O(n * k)

而单调队列可以把它优化到：

O(n)

单调队列的核心思想

以滑动窗口最大值为例，我们要维护一个单调递减队列。

队头永远保存当前窗口中的最大值下标。

为什么可以做到？

当新元素 nums[i] 进入窗口时：

这个过程会一直重复，直到队尾元素大于等于当前元素。
然后把当前下标加入队尾。

同时，由于窗口在向右移动，还要检查队头是否过期：

如果队头下标 <= i – k
说明它已经不在当前窗口内
需要从队头删除

所以单调队列每轮主要做两件事：

1. 从队尾删除不可能成为答案的元素
2. 从队头删除已经离开窗口的元素

为什么队列里通常存下标

单调队列里一般不直接存值，而是存数组下标。

原因有两个：

例如：

deque.peekFirst() <= i – k

这句判断的就是队头元素是否已经离开窗口。

单调队列保存的是当前窗口里仍然可能成为最大值或最小值的候选元素。

经典题型：滑动窗口最大值

题目：

给定整数数组 nums 和窗口大小 k，窗口每次向右移动一位，返回每个窗口中的最大值。

示例：

输入：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
输出：[3, 3, 5, 5, 6, 7]

暴力解法

最直接的做法是枚举每个窗口，然后在窗口内部找最大值。

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n – k + 1];

for (int i = 0; i <= n – k; i++) {
int max = nums[i];
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
ans[i] = max;
}

return ans;
}
}

复杂度：

• 时间复杂度：O(n * k)
• 空间复杂度：O(1)，不计输出数组

如果 n 和 k 都很大，这个解法很容易超时。

单调队列解法

我们维护一个单调递减队列。
队列里存的是数组下标，并且下标对应的值从队头到队尾递减。

每遍历到一个位置 i：

Java 代码实现

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n – k + 1];
Deque<Integer> deque = new ArrayDeque<>();

for (int i = 0; i < n; i++) {
while (!deque.isEmpty() && deque.peekFirst() <= i – k) {
deque.pollFirst();
}

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}

deque.offerLast(i);

if (i >= k – 1) {
ans[i – k + 1] = nums[deque.peekFirst()];
}
}

return ans;
}
}

代码逐行拆解

先看删除过期元素：

while (!deque.isEmpty() && deque.peekFirst() <= i – k) {
deque.pollFirst();
}

当前窗口的范围是：

[i – k + 1, i]

如果队头下标小于等于 i – k，说明它已经不在窗口内了，需要删除。

再看维护单调性：

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}

如果队尾元素比当前元素小，那么它以后不可能成为最大值。
因为当前元素更大，而且位置更靠右，会比它在窗口里存在得更久。

最后加入当前下标：

deque.offerLast(i);

当窗口长度达到 k 之后，队头就是当前窗口最大值：

if (i >= k – 1) {
ans[i – k + 1] = nums[deque.peekFirst()];
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(k)

虽然代码里有两个 while，但每个下标最多入队一次、出队一次。
所以整体时间复杂度是线性的。

单调队列如何解决窗口最小值

如果题目要求的是滑动窗口最小值，只需要把单调递减队列改成单调递增队列。

也就是把维护单调性的比较条件从：

nums[deque.peekLast()] < nums[i]

改成：

nums[deque.peekLast()] > nums[i]

完整代码如下：

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
public int[] minSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n – k + 1];
Deque<Integer> deque = new ArrayDeque<>();

for (int i = 0; i < n; i++) {
while (!deque.isEmpty() && deque.peekFirst() <= i – k) {
deque.pollFirst();
}

while (!deque.isEmpty() && nums[deque.peekLast()] > nums[i]) {
deque.pollLast();
}

deque.offerLast(i);

if (i >= k – 1) {
ans[i – k + 1] = nums[deque.peekFirst()];
}
}

return ans;
}
}

最大值和最小值的区别只有一处：

单调队列和单调栈的区别

上一篇讲了单调栈，这一篇讲单调队列。
它们名字很像，也确实有相似之处。

共同点：

• 都维护单调性
• 都会删除不可能成为答案的元素
• 都能把一些暴力查找优化到 O(n)

不同点：

可以这样理解：

单调栈更关注“谁能解决谁”，单调队列更关注“当前窗口里谁最有资格当答案”。

高频变形：带限制的最短子数组

单调队列除了滑动窗口最大值，也常用于一些前缀和问题。

例如有一类题：

给定数组和目标值，求和至少为 K 的最短连续子数组长度。

这类题会把原数组转成前缀和，然后在前缀和数组上维护一个单调队列。
核心思想仍然是：

• 队头用于尝试更新答案
• 队尾用于删除不可能更优的候选前缀和

这类题比滑动窗口最大值更难，后面讲前缀和进阶或动态规划优化时可以再单独展开。

初学阶段先把滑动窗口最大值吃透即可。

常见坑点：写单调队列最容易错在哪里

1. 队列里存了值，导致无法判断过期

错误思路：

Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(nums[i]);

这样虽然能比较大小，但无法知道这个值属于哪个下标，也就无法判断它是否离开窗口。

推荐写法：

Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(i);

通过下标既能取值：

nums[deque.peekFirst()]

也能判断过期：

deque.peekFirst() <= i – k

2. 先后顺序写错

一般推荐顺序是：

这个顺序清晰且不容易出错。

3. 把窗口边界写错

当前遍历到下标 i，窗口大小为 k，当前窗口左边界是：

i – k + 1

所以过期条件是：

deque.peekFirst() < i – k + 1

等价写法是：

deque.peekFirst() <= i – k

不要写成：

deque.peekFirst() < i – k

这会导致过期元素晚删一步。

模板总结：滑动窗口最大值

下面是最常用的单调队列模板。

int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n – k + 1];
Deque<Integer> deque = new ArrayDeque<>();

for (int i = 0; i < n; i++) {
while (!deque.isEmpty() && deque.peekFirst() <= i – k) {
deque.pollFirst();
}

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}

deque.offerLast(i);

if (i >= k – 1) {
ans[i – k + 1] = nums[deque.peekFirst()];
}
}

return ans;
}

记模板时不要只背代码，可以记住它背后的四句话：

队头过期就删除
队尾比当前弱就删除
当前下标进入队尾
窗口形成后队头就是答案

总结

队列的核心特征是：

先进先出

它适合处理按顺序推进的问题，例如 BFS、层序遍历和任务调度。

双端队列 Deque 可以同时操作队头和队尾，是单调队列的基础。

单调队列的核心作用是：

在滑动窗口中快速维护最大值或最小值。

你需要重点记住：

• 普通队列用于按顺序处理元素
• Deque 支持队头和队尾两端操作
• 单调队列通常存下标，而不是直接存值
• 求窗口最大值时维护单调递减队列
• 求窗口最小值时维护单调递增队列
• 队头负责给答案，队尾负责淘汰不可能成为答案的元素
• 每个元素最多入队一次、出队一次，所以整体是 O(n)