一、什么是单调队列
Mermaid · 渲染中（下方为源码）
graph LR W[滑动窗口] --> Q[单调队列维护极值] Q --> O[O(n) 求所有窗口最值] M[单调栈] --> N[下一个更大元素]
单调队列（Monotonic Deque） 是一种双端队列，其中元素始终保持单调递增或递减的顺序。它最经典的应用是在 O(n) 时间内求出所有固定大小窗口的最大值/最小值。
单调栈解决"下一个更大元素"，单调队列解决"窗口内最值"。
| 对比 | 单调栈 | 单调队列 |
|---|---|---|
| 结构 | 栈（一端进出） | 双端队列（两端操作） |
| 典型问题 | 下一个更大元素 | 滑动窗口最大值 |
| 过期处理 | 无需 | 需要移除窗口外元素 |
二、滑动窗口最大值
问题：给定数组和窗口大小 k，返回每个窗口的最大值。
2.1 暴力 O(nk)
// 每个窗口遍历 k 个元素找最大 → O(nk)2.2 单调队列 O(n)
维护一个递减双端队列（存下标），队头始终是当前窗口的最大值：
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // 存下标，值递减
for (int i = 0; i < n; i++) {
// 1. 移除窗口外的元素（队头过期）
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 2. 维护单调性：移除所有比当前值小的队尾
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
// 3. 当前元素入队
deque.offerLast(i);
// 4. 记录结果（窗口形成后）
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}