单调栈与单调队列：提前淘汰无用候选

我曾经把“单调栈与单调队列：提前淘汰无用候选”学成了一组互不相干的名词和代码。具体表现是：第一次见单调栈时，我只记住了“保持单调”，却不知道被弹出去的元素为什么以后再也没有资格成为答案。后来我尝试只保留一个问题：它到底在减少哪一种重复工作？顺着这个问题，整块知识才稳定下来。

单调栈和单调队列听起来像特殊技巧，但它们背后的思想很朴素：维护一个有顺序的候选集合，把未来不可能成为答案的元素提前删除。

它们常用于“下一个更大元素”“柱状图最大矩形”“滑动窗口最大值”等问题。

单调结构的核心

单调栈与单调队列

图：新元素进入时，把已经失去价值的候选提前弹掉

单调结构通常维护两种信息：

位置顺序：元素仍按原数组顺序进入。
值的单调性：栈或队列内部保持递增或递减。

它的强大之处在于，每个元素最多进一次、出一次，所以整体经常是 O(n)。

单调栈：下一个更大元素

给定数组，求每个元素右侧第一个比它大的元素。

int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            ans[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return ans;
}

栈里保存的是“还没找到下一个更大元素的位置”。当新元素 nums[i] 比栈顶大时，栈顶的答案就确定了。

单调队列：滑动窗口最大值

固定窗口里求最大值，如果每个窗口都重新扫描，复杂度是 O(nk)。单调队列可以做到 O(n)。

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;
}

队列里保存下标，队头是当前窗口最大值的位置。过期元素从队头删除，更小的新旧候选从队尾删除。

为什么可以弹掉元素

这是单调结构最重要的证明点。

以滑动窗口最大值为例，如果新元素 x 比队尾元素大，并且 x 的位置更靠右，那么队尾元素不可能在未来窗口中成为最大值：

当前它比 x 小。
未来它会比 x 更早过期。

所以可以安全弹掉。

常见问题

问题	结构
下一个更大元素	单调栈
每日温度	单调栈
柱状图最大矩形	单调栈
接雨水	双指针 / 单调栈
滑动窗口最大值	单调队列
队列中的最大值	单调队列

工程场景

单调队列思想可以用于实时指标：

最近 5 分钟最大 QPS。
最近 N 个采样点的最高延迟。
流式数据中的窗口最值。

不过工程里还要处理时间窗口、乱序数据和过期清理。算法题里的下标窗口，到了业务里往往变成时间戳窗口。

常见错误

栈里保存值，导致无法判断位置和过期。
单调方向搞反。
窗口过期条件写错。
使用 if 代替 while，只弹一个无效元素。
不理解为什么弹掉后不会漏答案。

面试题

单调栈为什么能找下一个更大元素？
单调队列为什么能维护窗口最大值？
为什么队列里通常保存下标而不是值？
每个元素最多进出一次，为什么整体是 O(n)？
单调栈和普通栈有什么区别？

小结

单调栈和单调队列的核心是候选淘汰。不是所有元素都值得留到最后，越早证明某个元素不可能成为答案，算法就越快。学会这个思想，很多看似需要双层循环的问题就能变成线性扫描。