单调栈与单调队列：有序性与时效性的博弈

一句话结论（30s）

单调栈解决「下一个更大/更小元素」靠的是有序性——新元素比栈顶大就把栈顶踢掉、保证栈内严格递减；单调队列解决「滑动窗口最大值」在有序性上再加时效性——即使元素再大，窗口滑过去就得从队头弹出，二者均摊都是 O(n)，因为每个元素只进出一次。

核心原理（2min）

• 单调栈：维持栈内严格递减，新元素大于栈顶则弹出并记录「右侧第一个更大」，剩余元素填 -1。
• 单调队列：队尾淘汰小于新元素的（保持递减）、队头淘汰过期的（<= i - k），队头即当前窗口最大值。
• 变体：下一个更小元素（< 判断）、更暖天气（存距离 i - idx）、循环数组（遍历 2n 取模）。

底层深入（5-10min）

单调栈：下一个更大元素

模板：维持栈内元素严格递减。新元素比栈顶大 → 一直弹出栈顶。

// 每个元素找到右侧第一个比它大的元素
int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();  // 存下标
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = nums[i];  // nums[i] 是 nums[idx] 的"右侧第一个更大"
        }
        stack.push(i);
    }
    // 栈中剩余元素 → 右侧没有比它大的 → 填 -1
    return result;
}

💭 思考：为什么「求下一个更大」能用栈，而且是递减栈？—— 从单个元素的角度想：一个元素要找「右边第一个比它大的」，意味着它一旦被某个更大的数「盖过」，答案就定了，后面再大的数也不关它的事。于是我们在遍历时，把「还没等到更大值」的元素堆在一起，来了一个新元素，它比谁大，谁就被它「清场」——这正好是栈的 LIFO。至于「递减」：栈里存的是「还没等到更大」的候选，它们必然从底到顶递减（一旦出现更大的，小的早被弹走了），所以新元素只需一路弹掉比它小的栈顶。

为什么是单调递减而不是递增？

单调递减栈（栈底大，栈顶小）。新元素比栈顶大 → 对于栈顶和它之前的较小元素，新元素是”右侧第一个更大”→ 弹出较小的元素，记录结果。新元素”踢掉”比它小的栈顶，保证栈内严格递减。

怎么想到用栈而不是数组遍历？ 因为”右侧第一个更大”本质是”每个元素被谁第一个盖过”——遍历到新元素时，它一次性解决所有比它小的、还在等待答案的旧元素，这种”后来者清场”的语义恰好就是栈的 LIFO。

变体

• 下一个更小元素：while nums[i] < nums[stack.peek()]
• 下一个更暖天气（距离）：result[idx] = i - idx
• 循环数组（连队）：遍历两遍数组（i < 2*n），下标取模

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

模板：维持队列内元素严格递减，过期元素从队头弹出。

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();  // 存下标
    for (int i = 0; i < n; i++) {
        // 1. 队头过期（窗口滑过去了）
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        // 2. 保持严格递减（小于新元素的都淘汰）
        while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) dq.pollLast();
        // 3. 新元素入队尾
        dq.offerLast(i);
        // 4. 窗口形成后，队头就是当前窗口最大值
        if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];
    }
    return result;
}

💭 思考：看到什么信号该想到单调队列？—— 单调栈只回答「右边第一个更大」，因为它不关心元素过没过期。但一旦题目加了「窗口」，最值就多了一个约束：再大的元素，窗口滑过去它也得滚。于是「有序性」（保持递减）之外，还要管「时效性」（队头过期就弹出），普通栈只有一端、管不了队头，只能上双端队列。所以信号是「窗口 + 最值（或范围约束）」，套路是「队尾维护有序、队头维护时效」，两步走：先淘汰队尾不配的，再淘汰队头过期的。

单调栈 vs 单调队列

单调栈的核心是”有序性”——凭什么某个元素被淘汰？新元素比它大/小，以后没它的事了。单调队列在有序性的基础上加了”时效性”——即使元素再大，窗口滑过去就没它的事了。

💭 思考：怎么判断一道题用栈还是队列？—— 核心只问一句：答案跟「位置 / 时间」有没有关系。没有时间维度的（「下一个更大」只看左右大小），栈的有序性就够了；一旦引入「窗口 / 范围」，某个元素「还在不在窗口内」就变得和「够不够大」同样重要，栈管不了「过期」，就得升级成双端队列。记住这句话：栈管「谁强谁留」，队列管「谁强谁留 + 谁过期谁走」。

章末提问

1. 单调栈为什么能求”下一个更大元素”，而且均摊是 O(n)？ 结论：因为每个元素最多进栈一次、出栈一次，while 里的弹出总次数有上限 n；所以看似二重循环，实际总操作是线性的。

2. 单调队列求滑动窗口最大值，队头过期为什么要用下标判断而不是值判断？ 结论：因为值可能重复，无法用值判断谁过期；存下标才能用 <= i - k 精确判定窗口是否已经滑过该元素。

3. 单调栈和单调队列的核心区别是什么？ 结论：单调栈只在一端操作、只关心有序性；单调队列在两端操作，除了有序性还多了窗口的时效性——队头会因过期被弹出，这是栈没有的维度。

时间复杂度：每个元素只 push/pop 一次

虽然是双重循环（while 嵌套在 for 内），但每个元素恰好进栈/队列一次、出一次。均摊 O(n)。

💭 思考：为什么代码里 while 套在 for 里，却仍是 O(n)？—— 别被二重循环骗了，关键看「每个元素总共进出几次」：入栈/入队一次、出栈/出队一次，while 里的弹出虽然单次可能弹很多，但把所有弹出的次数加起来不超过 n（每个元素只被弹一次）。所以总操作量是 O(n)，均摊到每次就是 O(1)。判断复杂度时，优先数「每个元素的总操作次数」，而不是数循环层数。