栈算法题解题思路与代码分析

1. 基础应用类（括号匹配 & 消消乐）

核心解题思路

这类题目利用栈的 LIFO 特性，遍历输入序列：

• 遇到“开启”类型的元素（如左括号、重复项的当前字符），将其压入栈中。
• 遇到“闭合”类型的元素（如右括号、与栈顶相同的字符、碰撞的方向），则与栈顶元素进行匹配或比较：若匹配则弹出栈顶（消去），否则根据规则压栈或返回错误。

经典例题：20. 有效的括号

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    // 用数组模拟栈
    const stack = [];
    // 哈希表存储括号的对应关系（右括号 -> 左括号）
    const map = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (let char of s) {
        // 如果是右括号
        if (map[char]) {
            // 栈顶元素必须是对应的左括号
            // 如果栈为空或者栈顶不匹配，则无效
            if (stack.length === 0 || stack.pop() !== map[char]) {
                return false;
            }
        } else {
            // 左括号直接入栈
            stack.push(char);
        }
    }

    // 遍历结束，栈应为空（所有左括号都被匹配）
    return stack.length === 0;
};

关键点：

• 利用哈希表建立右括号到左括号的映射，简化匹配判断。
• 遇到右括号时，栈顶元素必须是对应的左括号，否则直接返回 false。
• 最后检查栈是否为空，防止有未匹配的左括号。

2. 表达式求值类

核心解题思路

表达式求值通常需要两个栈（操作数栈和运算符栈），但对于后缀表达式（逆波兰表达式），只需一个栈即可。遇到数字则压栈，遇到运算符则弹出所需数量的操作数进行计算，并将结果重新压栈。

经典例题：150. 逆波兰表达式求值

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    const stack = [];

    for (let token of tokens) {
        // 如果是运算符
        if (['+', '-', '*', '/'].includes(token)) {
            // 弹出两个操作数（注意顺序：先弹出的是右操作数，后弹出的是左操作数）
            const right = stack.pop();
            const left = stack.pop();
            let result;

            switch (token) {
                case '+':
                    result = left + right;
                    break;
                case '-':
                    result = left - right;
                    break;
                case '*':
                    result = left * right;
                    break;
                case '/':
                    // 整数除法向零截断
                    result = left / right;
                    if (result < 0) {
                        result = Math.ceil(result);
                    } else {
                        result = Math.floor(result);
                    }
                    break;
                default:
                    break;
            }
            stack.push(result);
        } else {
            // 数字直接入栈（转换为数字类型）
            stack.push(Number(token));
        }
    }

    // 最终栈顶即为表达式结果
    return stack[0];
};

关键点：

• 注意操作数的顺序：先弹出的是右操作数，后弹出的是左操作数，对于减法和除法至关重要。
• 除法要求向零截断，可通过判断正负后使用 Math.floor 或 Math.ceil 实现。

3. 单调栈类

核心解题思路

单调栈通常用于解决下一个更大元素、每日温度等问题。栈内元素保持单调递增或递减。遍历数组时，当遇到破坏单调性的元素，就可以确定栈顶元素的“下一个更大/更小”的值，然后弹出栈顶，直到栈恢复单调。

经典例题：739. 每日温度

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    const stack = []; // 单调递减栈，存储温度的下标

    for (let i = 0; i < n; i++) {
        const temp = temperatures[i];
        // 当栈非空且当前温度大于栈顶温度时，说明找到了栈顶的下一个更高温度
        while (stack.length > 0 && temp > temperatures[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        // 将当前下标入栈（等待后续更高温度）
        stack.push(i);
    }

    return result;
};

关键点：

• 栈中存储的是下标，而不是温度本身，方便计算天数差。
• 栈保持单调递减，即从栈底到栈顶温度依次降低。当遇到比栈顶温度高的新温度时，就找到了栈顶的下一个更高温度。
• 最后栈中剩余的元素没有遇到更高温度，result 中对应的值保持为 0（初始化已填 0）。

4. 栈的设计类

核心解题思路

这类题目要求我们实现具有特殊功能的栈，如能在常数时间内获取最小值。常用技巧是辅助栈（同步存储当前最小值）或差值法（一个栈存储与当前最小值的差值）。

经典例题：155. 最小栈

var MinStack = function() {
    // 数据栈
    this.stack = [];
    // 辅助栈，栈顶始终存储当前最小值
    this.minStack = [];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    // 如果 minStack 为空，或 val 小于等于当前最小值，则将其入 minStack
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(val);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    const val = this.stack.pop();
    // 如果弹出的值恰好是当前最小值，minStack 也需要弹出
    if (val === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1];
};

关键点：

• 使用两个栈：stack 存放所有元素，minStack 存放历史最小值。
• push 时，只有当新元素小于等于当前最小值时才将其加入 minStack，保证 minStack 的栈顶始终是全局最小值。
• pop 时，如果弹出的元素等于 minStack 的栈顶，则 minStack 也要弹出，以便 minStack 的新栈顶成为剩余元素的最小值。

5. 进阶与特殊应用类

核心解题思路

这类题目将栈与其他算法（如贪心）结合，或者需要更复杂的数据结构设计。解题时需要灵活运用栈的特性，并考虑额外的约束条件。

经典例题：316. 去除重复字母

题目：给你一个字符串 s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

解题思路：单调栈 + 贪心。遍历字符串，用栈来维护最终结果。对于每个字符，如果它已经在栈中，则跳过；否则，当栈顶字符大于当前字符，且栈顶字符在后续还会出现时，就可以将栈顶弹出（保证字典序更小），然后将当前字符入栈。同时需要记录每个字符的剩余出现次数，以及是否已在栈中。

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
    // 记录每个字符的剩余出现次数
    const count = {};
    for (let char of s) {
        count[char] = (count[char] || 0) + 1;
    }

    const stack = [];
    // 记录栈中是否已包含某字符
    const inStack = {};

    for (let char of s) {
        // 每遍历一个字符，其剩余次数减1
        count[char]--;

        // 如果字符已在栈中，直接跳过
        if (inStack[char]) continue;

        // 当栈非空，且栈顶字符大于当前字符，且栈顶字符后面还会出现时，弹出栈顶
        while (stack.length > 0 && stack[stack.length - 1] > char && count[stack[stack.length - 1]] > 0) {
            // 将栈顶标记为不在栈中
            inStack[stack.pop()] = false;
        }

        // 当前字符入栈
        stack.push(char);
        inStack[char] = true;
    }

    return stack.join('');
};

关键点：

• 利用 count 记录每个字符剩余出现次数，用于判断后续是否还会出现。
• inStack 快速判断字符是否已在结果栈中，避免重复。
• 贪心思想：当栈顶字符比当前字符大且后面还会出现时，将其弹出，把当前字符压入，这样能保证字典序更小。
• 最终栈中字符的顺序就是去重后字典序最小的结果。

---

总结

栈的题目虽然多样，但核心都是利用其 LIFO 特性来维护某种“最近相关性”。建议按照以下顺序练习：

1. 基础应用：20. 有效的括号 → 1047. 删除字符串中的所有相邻重复项
2. 表达式求值：150. 逆波兰表达式求值 → 224. 基本计算器
3. 单调栈：739. 每日温度 → 84. 柱状图中最大的矩形
4. 栈的设计：155. 最小栈 → 232. 用栈实现队列
5. 进阶应用：316. 去除重复字母 → 895. 最大频率栈