单调队列问题
今天聊个有意思的结构：单调队列。
别被这名字吓到，听着好像挺学术，其实就是个双端队列（Deque），但咱们给它立了个规矩，让它里面的元素满足单调性。就这么简单。
这玩意儿有啥用？它专门解决一类问题，最经典的就是“滑动窗口最大值”。为了把这个结构讲透，咱们就拿这个问题开刀。
题目：滑动窗口最大值 (LeetCode 239)
给你一个整数数组 nums，有一个大小为 k 的滑动窗口，从数组的最左侧移动到最右侧。你只能看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回一个数组，包含每个窗口中的最大值。
举个例子： nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
窗口的移动过程和每个窗口的最大值如下：
| 窗口位置 | 最大值 |
| [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]。
好，问题清楚了。下面咱们用三种思路，一步一步把它干掉。
解法一：暴力，就是干！
拿到这题，第一反应是啥？别想那么多花里胡哨的，最朴素的想法就是模拟。
窗口怎么滑，我就怎么算。
搞一个循环，从数组的第一个位置开始，模拟窗口的起始点。这个窗口能滑到哪？最后一个窗口的起始点是
nums.length - k。在每个窗口内部，再搞一个循环，遍历这
k个数，找到最大值。把找到的最大值存到结果数组里。
思路简单直接，代码也就几行。
代码实现:
public int[] maxSlidingWindow_V1(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
int resultIndex = 0;
// 遍历所有窗口的起始位置
for (int i = 0; i <= n - k; i++) {
int maxVal = Integer.MIN_VALUE;
// 在当前窗口 [i, i + k - 1] 内找最大值
for (int j = i; j < i + k; j++) {
maxVal = Math.max(maxVal, nums[j]);
}
result[resultIndex++] = maxVal;
}
return result;
}
分析一下：
时间复杂度：外层循环跑了
N-K+1次，内层循环跑了K次。所以总的时间复杂度是 O(N * K)。空间复杂度：O(1) （如果不算结果数组的空间）。
这解法行不行？面试官要是看你这么写，肯定会接着问：“小伙子，这性能有点拉胯啊，有没有优化的空间？”
为啥拉胯？因为有大量重复计算。你看，当窗口从 [1, 3, -1] 滑到 [3, -1, -3] 时，3 和 -1 这俩哥们儿我们是不是又重新比较了一遍？这不浪费生命嘛。优化的方向，就是干掉这些重复计算。
解法二：稍微聪明点，用个优先队列
我们优化的目标是啥？快速找到一个集合里的最大值。什么数据结构干这事儿最快？堆（Heap），在Java里就是 PriorityQueue。
思路来了：
维护一个大小为
k的最大堆（Max Heap）。窗口向右滑动时，新进来的元素加到堆里，滑出去的元素从堆里删掉。
堆顶永远是当前窗口的最大值。
听起来很完美，对吧？但这里有个坑。Java的 PriorityQueue，删除一个指定元素的时间复杂度是 O(K)，因为它需要遍历去找到那个元素。这一下，整体复杂度又回到了 O(N * K)，白忙活了。
难道这条路走不通？别急，换个思路。我们不一定要真的从堆里“删除”那个滑出去的元素。我们可以玩个“懒删除”的把戏。
堆里不直接存值，我们存一个二元组
[value, index]。当窗口滑动时，我们只管把新元素
[nums[i], i]加进堆。每次取堆顶元素时，检查一下它的
index是不是已经过期了（即index小于当前窗口的左边界）。如果过期了，就把它扔掉（
poll()），继续看下一个堆顶元素，直到找到一个在窗口内的为止。这个元素就是当前窗口的最大值。
这样一来，每个元素最多进堆一次，出堆一次。
代码实现:
import java.util.PriorityQueue;
public int[] maxSlidingWindow_V2(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
// 创建一个最大堆，存放 [value, index]
// 按照 value 降序排列
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(a, b) -> b[0] - a[0]
);
for (int i = 0; i < n; i++) {
// 新元素入堆
maxHeap.offer(new int[]{nums[i], i});
// 当窗口形成了 (即遍历到了第 k-1 个元素)
if (i >= k - 1) {
// 检查堆顶元素是否在当前窗口内
// 窗口左边界是 i - k + 1
while (maxHeap.peek()[1] < i - k + 1) {
maxHeap.poll(); // 移除过期的元素
}
// 此时堆顶就是当前窗口的最大值
result[i - k + 1] = maxHeap.peek()[0];
}
}
return result;
}
分析一下：
时间复杂度：每个元素都要进堆、出堆一次。堆操作的时间复杂度是 O(logK)。所以总的时间复杂度是 O(N logK)。比 O(N K) 强多了。
空间复杂度：堆里最多可能存放
k个元素，所以是 O(K)。
这个解法已经相当不错了，大部分情况下都能过。但面试官是魔鬼，他会继续追问：“还有没有可能更快？比如 O(N)？”
O(N)？这意味着每次窗口滑动，我们得用 O(1) 的时间（摊还）找到最大值。logK 都不行。这就得请出我们今天的主角了。
解法三：终极武器，单调队列登场！
回想一下我们的痛点：在窗口滑动的过程中，我们需要维护一组“候选”的最大值。
思考一个问题：在窗口 [..., a, ..., b, ...] 中，如果 a 在 b 的左边（index(a) < index(b)），并且 a 的值还比 b 小（value(a) <= value(b)），那么 a 这个元素还有可能成为未来任何一个包含 b 的窗口的最大值吗？
不可能！
为啥？因为只要 b 还在窗口里，a 就绝对不是最大值，因为它被 b 压得死死的。而且 a 比 b 更早离开窗口。所以，a 这种“又老又小”的元素，对我们找最大值来说，是完全没用的，可以直接扔掉！
这个发现就是单调队列的精髓。我们可以维护一个队列，里面存放元素的下标。并遵守以下规则：
队列里的下标对应的元素值，必须是单调递减的。
队头（front）永远是当前窗口最大值的下标。
我们用一个双端队列（Deque）来实现。当一个新元素 nums[i] 要进来时：
入口端（队尾）：从队尾开始，把所有比
nums[i]小的元素的下标都从队列里“请”出去。为啥？因为nums[i]比它们都“年轻”（下标更大），还比它们都“能打”（值更大），这些老家伙就没用了。处理完之后，再把nums[i]的下标i加到队尾。出口端（队头）：在记录结果之前，检查一下队头的下标是不是已经过期了（滑出了窗口的左边界）。如果是，就把它从队头移除。
获取最大值：经过上面两步，队头的下标就是当前窗口最大值的下标。
整个过程，每个元素的下标最多进队一次、出队一次。
代码实现:
import java.util.Deque;
import java.util.LinkedList;
public int[] maxSlidingWindow_V3(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
int resultIndex = 0;
// Deque 存放的是数组的下标
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 1. 维护队列的单调性：从队尾移除所有小于当前元素的下标
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
// 2. 将当前元素的下标加入队尾
deque.addLast(i);
// 3. 移除过期的队头下标
if (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 4. 当窗口形成后，队头就是当前窗口最大值的下标
if (i >= k - 1) {
result[resultIndex++] = nums[deque.peekFirst()];
}
}
return result;
}
分析一下：
时间复杂度：O(N)。虽然
for循环里有个while，但每个元素的下标最多只会被加入队列一次，移除一次。所以while循环的总执行次数不会超过 N。摊还下来，每次循环的操作是 O(1)。空间复杂度：O(K)。队列里最多存放
k个下标。
完美！这已经是这个问题最优的时间和空间复杂度了。
总结
咱们今天从一个经典的滑动窗口问题入手，体验了三种不同层次的解法：
暴力解 O(N * K)：简单无脑，但重复计算太多，是优化的起点。
优先队列 O(N * logK)：想到了用合适的数据结构来优化查找，思路走对了，但没到极致。
单调队列 O(N)：通过深入分析问题的内在逻辑，发现并剔除了“无效”的候选者，只维护一个单调递减的“精英”候选队列，最终达到了线性时间复杂度。
这就是从暴力到最优的思考过程。单调队列这个结构，本质上就是一种通过维持单调性来不断淘汰无效解，从而高效找到最优解的思维工具。搞懂了这个，以后再遇到类似“在某个范围内找最值”的问题，思路就清晰了。好的，开整。
单调队列？搞定它！从暴力解到最优解，彻底给你讲明白了
今天聊个有意思的结构：单调队列。
别被这名字吓到，听着好像挺学术，其实就是个双端队列（Deque），但咱们给它立了个规矩，让它里面的元素满足单调性。就这么简单。
这玩意儿有啥用？它专门解决一类问题，最经典的就是“滑动窗口最大值”。为了把这个结构讲透，咱们就拿这个问题开刀。
题目：滑动窗口最大值 (LeetCode 239)
给你一个整数数组 nums，有一个大小为 k 的滑动窗口，从数组的最左侧移动到最右侧。你只能看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回一个数组，包含每个窗口中的最大值。
举个例子： nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
窗口的移动过程和每个窗口的最大值如下：
| 窗口位置 | 最大值 |
| [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]。
好，问题清楚了。下面咱们用三种思路，一步一步把它干掉。
解法一：暴力，就是干！
拿到这题，第一反应是啥？别想那么多花里胡哨的，最朴素的想法就是模拟。
窗口怎么滑，我就怎么算。
搞一个循环，从数组的第一个位置开始，模拟窗口的起始点。这个窗口能滑到哪？最后一个窗口的起始点是
nums.length - k。在每个窗口内部，再搞一个循环，遍历这
k个数，找到最大值。把找到的最大值存到结果数组里。
思路简单直接，代码也就几行。
代码实现:
public int[] maxSlidingWindow_V1(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
int resultIndex = 0;
// 遍历所有窗口的起始位置
for (int i = 0; i <= n - k; i++) {
int maxVal = Integer.MIN_VALUE;
// 在当前窗口 [i, i + k - 1] 内找最大值
for (int j = i; j < i + k; j++) {
maxVal = Math.max(maxVal, nums[j]);
}
result[resultIndex++] = maxVal;
}
return result;
}
分析一下：
时间复杂度：外层循环跑了
N-K+1次，内层循环跑了K次。所以总的时间复杂度是 O(N * K)。空间复杂度：O(1) （如果不算结果数组的空间）。
这解法行不行？面试官要是看你这么写，肯定会接着问：“小伙子，这性能有点拉胯啊，有没有优化的空间？”
为啥拉胯？因为有大量重复计算。你看，当窗口从 [1, 3, -1] 滑到 [3, -1, -3] 时，3 和 -1 这俩哥们儿我们是不是又重新比较了一遍？这不浪费生命嘛。优化的方向，就是干掉这些重复计算。
解法二：稍微聪明点，用个优先队列
我们优化的目标是啥？快速找到一个集合里的最大值。什么数据结构干这事儿最快？堆（Heap），在Java里就是 PriorityQueue。
思路来了：
维护一个大小为
k的最大堆（Max Heap）。窗口向右滑动时，新进来的元素加到堆里，滑出去的元素从堆里删掉。
堆顶永远是当前窗口的最大值。
听起来很完美，对吧？但这里有个坑。Java的 PriorityQueue，删除一个指定元素的时间复杂度是 O(K)，因为它需要遍历去找到那个元素。这一下，整体复杂度又回到了 O(N * K)，白忙活了。
难道这条路走不通？别急，换个思路。我们不一定要真的从堆里“删除”那个滑出去的元素。我们可以玩个“懒删除”的把戏。
堆里不直接存值，我们存一个二元组
[value, index]。当窗口滑动时，我们只管把新元素
[nums[i], i]加进堆。每次取堆顶元素时，检查一下它的
index是不是已经过期了（即index小于当前窗口的左边界）。如果过期了，就把它扔掉（
poll()），继续看下一个堆顶元素，直到找到一个在窗口内的为止。这个元素就是当前窗口的最大值。
这样一来，每个元素最多进堆一次，出堆一次。
代码实现:
import java.util.PriorityQueue;
public int[] maxSlidingWindow_V2(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
// 创建一个最大堆，存放 [value, index]
// 按照 value 降序排列
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(a, b) -> b[0] - a[0]
);
for (int i = 0; i < n; i++) {
// 新元素入堆
maxHeap.offer(new int[]{nums[i], i});
// 当窗口形成了 (即遍历到了第 k-1 个元素)
if (i >= k - 1) {
// 检查堆顶元素是否在当前窗口内
// 窗口左边界是 i - k + 1
while (maxHeap.peek()[1] < i - k + 1) {
maxHeap.poll(); // 移除过期的元素
}
// 此时堆顶就是当前窗口的最大值
result[i - k + 1] = maxHeap.peek()[0];
}
}
return result;
}
分析一下：
时间复杂度：每个元素都要进堆、出堆一次。堆操作的时间复杂度是 O(logK)。所以总的时间复杂度是 O(N logK)。比 O(N K) 强多了。
空间复杂度：堆里最多可能存放
k个元素，所以是 O(K)。
这个解法已经相当不错了，大部分情况下都能过。但面试官是魔鬼，他会继续追问：“还有没有可能更快？比如 O(N)？”
O(N)？这意味着每次窗口滑动，我们得用 O(1) 的时间（摊还）找到最大值。logK 都不行。这就得请出我们今天的主角了。
解法三：终极武器，单调队列登场！
回想一下我们的痛点：在窗口滑动的过程中，我们需要维护一组“候选”的最大值。
思考一个问题：在窗口 [..., a, ..., b, ...] 中，如果 a 在 b 的左边（index(a) < index(b)），并且 a 的值还比 b 小（value(a) <= value(b)），那么 a 这个元素还有可能成为未来任何一个包含 b 的窗口的最大值吗？
不可能！
为啥？因为只要 b 还在窗口里，a 就绝对不是最大值，因为它被 b 压得死死的。而且 a 比 b 更早离开窗口。所以，a 这种“又老又小”的元素，对我们找最大值来说，是完全没用的，可以直接扔掉！
这个发现就是单调队列的精髓。我们可以维护一个队列，里面存放元素的下标。并遵守以下规则：
队列里的下标对应的元素值，必须是单调递减的。
队头（front）永远是当前窗口最大值的下标。
我们用一个双端队列（Deque）来实现。当一个新元素 nums[i] 要进来时：
入口端（队尾）：从队尾开始，把所有比
nums[i]小的元素的下标都从队列里“请”出去。为啥？因为nums[i]比它们都“年轻”（下标更大），还比它们都“能打”（值更大），这些老家伙就没用了。处理完之后，再把nums[i]的下标i加到队尾。出口端（队头）：在记录结果之前，检查一下队头的下标是不是已经过期了（滑出了窗口的左边界）。如果是，就把它从队头移除。
获取最大值：经过上面两步，队头的下标就是当前窗口最大值的下标。
整个过程，每个元素的下标最多进队一次、出队一次。
代码实现:
import java.util.Deque;
import java.util.LinkedList;
public int[] maxSlidingWindow_V3(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
int resultIndex = 0;
// Deque 存放的是数组的下标
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 1. 维护队列的单调性：从队尾移除所有小于当前元素的下标
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
// 2. 将当前元素的下标加入队尾
deque.addLast(i);
// 3. 移除过期的队头下标
if (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 4. 当窗口形成后，队头就是当前窗口最大值的下标
if (i >= k - 1) {
result[resultIndex++] = nums[deque.peekFirst()];
}
}
return result;
}
分析一下：
时间复杂度：O(N)。虽然
for循环里有个while，但每个元素的下标最多只会被加入队列一次，移除一次。所以while循环的总执行次数不会超过 N。摊还下来，每次循环的操作是 O(1)。空间复杂度：O(K)。队列里最多存放
k个下标。
完美！这已经是这个问题最优的时间和空间复杂度了。
总结
暴力解 O(N * K)：简单无脑，但重复计算太多，是优化的起点。
优先队列 O(N * logK)：想到了用合适的数据结构来优化查找，思路走对了，但没到极致。
单调队列 O(N)：通过深入分析问题的内在逻辑，发现并剔除了“无效”的候选者，只维护一个单调递减的“精英”候选队列，最终达到了线性时间复杂度。
这就是从暴力到最优的思考过程。单调队列这个结构，本质上就是一种通过维持单调性来不断淘汰无效解，从而高效找到最优解的思维工具。搞懂了这个，以后再遇到类似“在某个范围内找最值”的问题，思路就清晰了。