一、栈与队列：单调栈、单调队列与经典例题

说实话，栈和队列这两个数据结构，很多同学觉得太基础了。不就是「先进后出」和「先进先出」嘛？但真正到了算法题里，它们能玩出的花样可不少。我个人习惯把栈和队列比作「管道」——栈是死胡同，进去得原路退出来；队列是单向通道，排着队往前走。

今天咱们重点聊两个进阶玩法：单调栈和单调队列。这两个东西，说白了就是在普通栈/队列的基础上，加了一条「内部元素必须单调」的约束。听起来简单，但用好了能解决一大批看似复杂的问题。

1.1 单调栈：找下一个更大/更小元素

先说说单调栈。我刚开始刷题时，遇到「下一个更大元素」这类题，第一反应就是暴力双重循环。后来发现，单调栈能把 O(n²) 降到 O(n)，效率提升非常明显。

核心思想：维护一个栈，栈内元素保持单调递增或单调递减。遍历数组时，如果当前元素破坏了单调性，就不断弹出栈顶，直到重新满足单调条件。

举个例子，经典题「每日温度」：给你一个温度数组，返回每个温度需要等几天才能遇到更高的温度。

// 单调栈解法（递增栈）
function dailyTemperatures(temperatures) {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    const stack = []; // 存下标，栈内温度递减

    for (let i = 0; i < n; i++) {
        // 当前温度比栈顶高，说明找到了答案
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    return result;
}

你看，代码其实很短。关键点在于：栈里存的是下标，不是值。为什么？因为我们需要计算距离，存下标才能算出差值。这是我踩过的坑——一开始存值，结果发现距离算不出来，又得回头改。

1.2 单调队列：滑动窗口的利器

单调队列和单调栈很像，但多了一个操作——队头出队。因为队列有「先进先出」的特性，所以特别适合处理滑动窗口问题。

我记得有一次面试，面试官让我手写「滑动窗口最大值」。我当时心想：这不就是每个窗口暴力扫一遍吗？结果面试官说：「你的复杂度是 O(nk)，能不能优化到 O(n)？」嗯，这时候单调队列就派上用场了。

核心思想：维护一个双端队列，队头始终是当前窗口的最大值（或最小值）。每次窗口滑动时，做两件事：

• 把新元素从队尾加入，同时把队尾比它小的元素全部弹出
• 检查队头是否已经滑出窗口，如果是则弹出队头

// 滑动窗口最大值 - 单调队列解法
function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // 存下标，队头到队尾递减

    for (let i = 0; i < nums.length; i++) {
        // 1. 队尾维护单调递减
        while (deque.length > 0 && nums[i] > nums[deque[deque.length - 1]]) {
            deque.pop();
        }
        deque.push(i);

        // 2. 队头如果滑出窗口，弹出
        if (deque[0] <= i - k) {
            deque.shift();
        }

        // 3. 窗口形成后，记录结果
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    return result;
}

这里有个细节要注意：队头弹出用的是 shift()，但 JavaScript 里 shift() 是 O(n) 的。如果追求极致性能，可以用双向链表或者用数组模拟双端队列（维护头尾指针）。不过一般面试中，用数组的 shift() 也能过，毕竟数据量不大。

1.3 经典例题：有效括号

「有效括号」这道题，可以说是栈的入门必做题。但你别小看它，很多变种题都是从它衍生出来的。

题目：给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串，判断是否有效。

规则很简单：左括号必须用同类型的右括号闭合，且顺序正确。

function isValid(s) {
    const stack = [];
    const map = {
        ')': '(',
        '}': '{',
        ']': '['
    };

    for (let char of s) {
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else {
            // 遇到右括号，检查栈顶是否匹配
            if (stack.length === 0 || stack.pop() !== map[char]) {
                return false;
            }
        }
    }
    // 最后栈必须为空
    return stack.length === 0;
}

你想想看，为什么最后要检查栈是否为空？因为可能出现「((」这种只有左括号的情况。嗯，这个细节很容易漏掉。

1.4 知识体系总览

下面这张图，我把本章的核心知识点串起来了。你看一眼，心里就有数了。

1.5 避坑指南与经验总结

最后，分享几个我实际工作中遇到的坑：

• 栈溢出问题：递归实现栈操作时，如果数据量很大（比如 10 万级），小心调用栈溢出。我建议用迭代代替递归。
• 单调队列的边界：窗口滑动时，队头下标等于 i - k 时就要弹出。注意是「等于」还是「小于等于」？我习惯用 deque[0] <= i - k，这样更安全。
• 性能陷阱：JavaScript 的数组 shift() 是 O(n) 的。如果数据量超过 10 万，建议用 index 指针模拟队列，或者用 new LinkedList()。

---

公众号:蓝海资料掘金营，微信deep3321