单调队列算法详解（附 Java 实战代码）

目录

一、什么是单调队列？

二、核心规则（以滑动窗口最大值为例）

三、经典例题：滑动窗口最大值

题目描述

Java 完整代码

代码核心解释

四、扩展：滑动窗口最小值

五、单调队列适用场景

六、总结

一、什么是单调队列？

单调队列= 队列 + 队列内元素严格单调递增 / 递减，是一种双端队列（Deque）实现的特殊数据结构。

核心特性：

1. 队列头部始终是当前窗口 / 区间的最优值（最大值 / 最小值）
2. 队列尾部用于添加新元素，维护单调性
3. 插入 / 删除操作均为O(1)，整体处理数组时间复杂度O(n)

它的核心用途：解决滑动窗口最值问题（暴力法 O (n・k)，单调队列优化到 O (n)）。

二、核心规则（以滑动窗口最大值为例）

我们维护一个单调递减队列：

1. 入队：新元素从队尾入队，把所有比它小的元素全部弹出（这些元素不可能成为后续窗口的最大值），再加入新元素下标
2. 出队：如果队首元素下标超出窗口左边界，从队首弹出
3. 取值：窗口形成后，队首元素就是当前窗口最大值

三、经典例题：滑动窗口最大值

题目描述

给定数组nums，大小为k的滑动窗口从数组最左侧移到最右侧，返回每个窗口的最大值。

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

Java 完整代码

import java.util.ArrayDeque; import java.util.Deque; public class MonotonicQueue { public int[] maxSlidingWindow(int[] nums, int k) { // 边界判断 if (nums == null || nums.length == 0 || k <= 0) { return new int[0]; } int n = nums.length; // 结果数组长度：n - k + 1 int[] res = new int[n - k + 1]; int index = 0; // 双端队列：存储元素下标（方便判断是否超出窗口） Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // 规则1：队首元素超出窗口左边界，移除 // 窗口左边界 = i - k + 1，队首 < 左边界 则过期 while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) { deque.pollFirst(); } // 规则2：维护单调递减队列 // 新元素 >= 队尾元素，队尾弹出（不可能成为最大值） while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { deque.pollLast(); } // 加入当前元素下标 deque.offerLast(i); // 规则3：窗口形成后（i >= k-1），记录队首最大值 if (i >= k - 1) { res[index++] = nums[deque.peekFirst()]; } } return res; } // 测试 public static void main(String[] args) { MonotonicQueue mq = new MonotonicQueue(); int[] nums = {1,3,-1,-3,5,3,6,7}; int k = 3; int[] result = mq.maxSlidingWindow(nums, k); System.out.print("滑动窗口最大值："); for (int num : result) { System.out.print(num + " "); } // 输出：3 3 5 5 6 7 } }

代码核心解释

1. 队列存下标：方便判断元素是否超出窗口范围
2. 维护递减：保证队首永远是当前窗口最大值
3. 窗口形成条件：i >= k-1，此时开始收集结果
4. 时间复杂度：每个元素仅入队 / 出队一次，O (n)

四、扩展：滑动窗口最小值

只需修改维护规则，改为单调递增队列：

// 维护单调递增队列（最小值） while (!deque.isEmpty() && nums[i] <= nums[deque.peekLast()]) { deque.pollLast(); }

五、单调队列适用场景

1. 滑动窗口最值（最经典）
2. 子数组区间最值问题
3. 动态维护区间极值
4. 优化 DP（单调队列优化 DP）

六、总结

1. 本质：用双端队列维护单调序列，保证 O (1) 获取最值
2. 核心操作：队首过期删除、队尾维护单调性、窗口形成取队首
3. 优势：把 O (n・k) 暴力优化到 O (n)
4. Java 实现：用ArrayDeque存下标，效率最高