栈高频面试题全解析：7道必刷题目+详细解题思路

7道经典面试题，从基础到单调栈，覆盖括号匹配、路径处理、逆波兰表达式等核心场景，附完整 C++ 实现。

一、有效的括号 简单

LeetCode 20. 有效的括号

题目描述

给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串 s，判断字符串是否有效。括号必须以正确的顺序关闭，且每个左括号都有对应的右括号。

示例：

输入: s = "()[]{}"   →  输出: true
输入: s = "(]"       →  输出: false
输入: s = "([)]"     →  输出: false
输入: s = "([])"     →  输出: true

解题思路

利用栈的「后进先出」特性进行括号匹配，遍历字符串处理两种情况：

• 遇到左括号 (、[、{ ：将对应的右括号压栈（压期望匹配的值）；
• 遇到右括号：检查栈顶是否为该右括号，若不匹配或栈为空，返回 false；
• 遍历结束后，栈为空则说明全部匹配，返回 true。

C++ 实现

class Solution {

public:
    bool isValid(string s) {

        stack<char> st;
        for (char c : s) {

            if      (c == '(') st.push(')');
            else if (c == '[') st.push(']');
            else if (c == '{') st.push('}');
            // 遇到右括号：栈空或不匹配
            else if (st.empty() || st.top() != c) return false;
            else st.pop();
        }
        return st.empty();
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

二、最小栈 中等

LeetCode 155. 最小栈

题目描述

设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();  // 返回 -3
minStack.pop();
minStack.top();     // 返回 0
minStack.getMin();  // 返回 -2

解题思路

维护两个栈：一个主栈存数据，一个辅助最小栈 minStack 同步记录当前历史最小值。

• 每次 push 时，同时向 minStack 压入「当前值与栈顶的较小值」；
• pop 时两个栈同步弹出；
• getMin 直接返回 minStack 栈顶，保证 O(1)。

C++ 实现

class MinStack {

    stack<int> st, minSt;
public:
    MinStack() {
  }

    void push(int val) {

        st.push(val);
        // minSt 记录截至此刻的最小值
        if (minSt.empty() || val <= minSt.top())
            minSt.push(val);
        else
            minSt.push(minSt.top());
    }

    void pop() {

        st.pop();
        minSt.pop();
    }

    int top()    {
   return st.top(); }
    int getMin() {
   return minSt.top(); }
};

复杂度分析

• 时间复杂度：O(1)（每次操作）
• 空间复杂度：O(n)

三、字符串解码 中等

LeetCode 394. 字符串解码

题目描述

给定一个经过编码的字符串，返回解码后的字符串。编码规则为 k[encoded_string]，表示方括号内的字符串被重复 k 次。

输入: "3[a]2[bc]"     →  输出: "aaabcbc"
输入: "3[a2]"      →  输出: "accaccacc"
输入: "2[abc]3[cd]ef" →  输出: "abcabccdcdcdef"
输入: "abc3[cd]xyz" →  输出: "abccdcdcdxyz"

解题思路

用两个栈分别存储数字和字符串，遍历字符处理四种情况：

• 遇到数字：累积构成完整数字 k；
• 遇到 [：将当前 k 和当前字符串分别压栈，然后重置两者；
• 遇到 ]：弹出栈顶次数和字符串，将当前字符串重复后拼接；
• 遇到普通字母：追加到当前字符串。

C++ 实现

class Solution {

public:
    string decodeString(string s) {

        stack<int>    numSt;
        stack<string> strSt;
        string cur = "";
        int k = 0;

        for (char c : s) {

            if (isdigit(c)) {

                k = k * 10 + (c - '0');
            } else if (c == '[') {

                numSt.push(k);
                strSt.push(cur);
                k = 0; cur = "";
            } else if (c == ']') {

                int    times = numSt.top(); numSt.pop();
                string prev  = strSt.top(); strSt.pop();
                for (int i = 0; i < times; i++) prev += cur;
                cur = prev;
            } else {

                cur += c;
            }
        }
        return cur;
    }
};

复杂度分析

• 时间复杂度：O(n)（n 为解码后字符串长度）
• 空间复杂度：O(n)

四、简化路径 中等

LeetCode 71. 简化路径

题目描述

给你一个 Unix 风格的绝对路径字符串 path，请将其转化为规范路径（最简形式）。规范路径需满足：以 / 开头，目录名之间只有单个 /，路径不以 / 结尾，不含 . 或 ..。

输入: "/home/"              →  输出: "/home"
输入: "/../"                →  输出: "/"
输入: "/home//foo/"         →  输出: "/home/foo"
输入: "/a/./b/../../c/"     →  输出: "/c"

解题思路

以 / 为分隔符切分路径，逐段处理：

• 空串或 .：跳过（当前目录，不影响路径）；
• ..：若栈非空则弹出（回到父目录）；
• 其他目录名：压入栈（进入子目录）。

最后将栈中目录名用 / 拼接，加上开头的 / 即为结果。

C++ 实现

class Solution {

public:
    string simplifyPath(string path) {

        vector<string> st;
        stringstream ss(path);
        string token;

        while (getline(ss, token, '/')) {

            if (token == "" || token == ".") {

                continue;
            } else if (token == "..") {

                if (!st.empty()) st.pop_back();
            } else {

                st.push_back(token);
            }
        }

        string res = "";
        for (auto& s : st) res += "/" + s;
        return res.empty() ? "/" : res;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

五、逆波兰表达式求值 中等

LeetCode 150. 逆波兰表达式求值

题目描述

根据逆波兰表示法（后缀表达式），求表达式的值。有效算符包括 +、-、*、/，除法向零截断。

输入: ["2","1","+","3","*"]         →  输出: 9    // ((2+1)*3)
输入: ["4","13","5","/","+"]        →  输出: 6    // (4+(13/5))
输入: ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]  →  输出: 22    // ((10 * (6 / ((9 + 3) * -11))) + 17) + 5

解题思路

后缀表达式天然适合栈处理：操作数入栈，遇运算符弹出两个数计算后压回栈。

• 遇到数字：转为整数压栈；
• 遇到运算符：弹出 b（后弹）和 a（先弹），计算 a op b，结果入栈；
• 遍历完成后，栈顶即为最终答案。

️ 注意弹出顺序：先弹出的是右操作数 b，后弹出的是左操作数 a。

C++ 实现

class Solution {

public:
    int evalRPN(vector<string>& tokens) {

        stack<long long> st;
        for (auto& t : tokens) {

            if (t == "+" || t == "-" || t == "*" || t == "/") {

                long long b = st.top(); st.pop();
                long long a = st.top(); st.pop();
                if      (t == "+") st.push(a + b);
                else if (t == "-") st.push(a - b);
                else if (t == "*") st.push(a * b);
                else               st.push(a / b);
            } else {

                st.push(stoll(t));
            }
        }
        return (int)st.top();
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

六、每日温度 中等

LeetCode 739. 每日温度

题目描述

给定一个整数数组 temperatures 表示每天的温度，返回数组 answer，其中 answer[i] 表示第 i 天后需要等几天才能等到更高温度。若之后都不会升高，则为 0。

输入: [73,74,75,71,69,72,76,73]  →  输出: [1,1,4,2,1,1,0,0]
输入: [30,40,50,60]               →  输出: [1,1,1,0]
输入: [30,60,90]                  →  输出: [1,1,0]

解题思路：单调递减栈

维护一个单调递减栈，存储尚未找到更高温度的日期下标：

1. 遍历到第 i 天，若当前温度 > 栈顶对应温度：
   • 弹出栈顶 j，令 answer[j] = i - j（等待天数）；
   • 重复弹出，直到栈空或栈顶温度 ≥ 当前温度；
2. 将 i 压栈，等待未来更高温度。

这是单调栈「找下一个更大元素」的经典模板。

C++ 实现

class Solution {

public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {

        int n = temperatures.size();
        vector<int> ans(n, 0);
        stack<int> st; // 存下标，栈内温度单调递减

        for (int i = 0; i < n; i++) {

            // 当前温度更高，弹出等待中的日期
            while (!st.empty() &&
                   temperatures[i] > temperatures[st.top()]) {

                int j = st.top(); st.pop();
                ans[j] = i - j;
            }
            st.push(i);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n)（每个元素最多入栈出栈各一次）
• 空间复杂度：O(n)

七、柱状图中最大的矩形 困难

LeetCode 84. 柱状图中最大的矩形

题目描述

给定 n 个非负整数表示柱状图中各柱子的高度，每个柱子宽度为 1，求能勾勒出的矩形的最大面积。

输入: heights = [2,1,5,6,2,3]  →  输出: 10
输入: heights = [2,4]           →  输出: 4

解题思路：单调递增栈 + 哨兵

核心思想： 对于每根柱子，以它为高度的最大矩形，向左右延伸到第一个比它矮的柱子为止。

1. 维护单调递增栈（存下标），栈内高度从底到顶单调递增；
2. 遇到比栈顶矮的柱子 i 时：
   • 弹出栈顶 mid，高度 h = heights[mid]；
   • 宽度 w = i - 新栈顶 - 1（左右第一个比 h 矮的柱子之间的距离）；
   • 更新最大面积 h * w；
3. 首尾添加高度为 0 的哨兵柱，确保所有柱子都能被弹出处理。

通俗解释

先搞懂核心问题：找 “能撑多宽”
要算一个柱子能组成的最大矩形，关键就两件事：

• 高度：就是柱子自己的高度（比如高度 5 的柱子，矩形高度最多就是 5）；
• 宽度：这个柱子能 “左右延伸” 多远 ——往左能到第一个比它矮的柱子右边，往右能到第一个比它矮的柱子左边（再远就撑不住了，矮柱子托不起这个高度）。

为啥用 “单调递增栈”？
单调递增栈的作用，就是帮我们 “记住” 每个柱子左边第一个比它矮的柱子，同时在遍历中 “发现” 右边第一个比它矮的柱子

用 “排队” 的例子理解栈的逻辑：
假设我们让柱子按 “身高递增” 的顺序排队（栈里存的是柱子的位置）：

1. 新来的柱子比队尾的柱子高 → 直接排到队尾（因为队尾柱子的右边还没遇到更矮的，先记着）；
2. 新来的柱子比队尾的柱子矮 → 坏事了！队尾柱子的 “右边界” 找到了（就是这个新来的矮柱子），弹出队尾柱子，而队尾柱子的 “左边界” 就是现在的新队尾（之前排的更矮的柱子）。

这时候就能算队尾柱子的最大矩形了 —— 因为它的左右边界都找到了！

结合示例（[0,2,1,5,6,2,3,0]）再通俗说：

• 遍历到下标 5（高度 2）时，栈里是 [0,2,3,4]（对应高度 0、1、5、6）；
• 新来的 2 比栈尾的 6 矮 → 6 的右边界是 5，左边界是 3（高度 5），所以 6 能撑的宽度是 5-3-1=1，面积 6×1=6；
• 弹出 6 后，新来的 2 还比栈尾的 5 矮 → 5 的右边界是 5，左边界是 2（高度 1），所以 5 能撑的宽度是 5-2-1=2，面积 5×2=10；
• 现在栈尾是 2（高度 1），2≥1，不用算了，把 5（高度 2）排到队尾就行。

最后解释：为啥要加 “哨兵（高度 0）”？
哨兵就是两个 “最矮的柱子”（身高 0），放在队伍头尾，解决两个 “漏算” 问题：

1. 开头加 0 → 保证第一个柱子也有 “左边界”（不会出现栈空没法算宽度的情况）；
2. 结尾加 0 → 保证所有柱子都能被算到（0 是最矮的，遍历到它时，栈里剩下的所有柱子都会因为 “遇到更矮的” 被弹出计算，不会漏掉）。

C++ 实现

class Solution {

public:
    int largestRectangleArea(vector<int>& heights) {

        // 添加首尾哨兵，高度为 0
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int n = heights.size();
        stack<int> st; // 单调递增栈（存下标）
        int maxArea = 0;

        for (int i = 0; i < n; i++) {

            while (!st.empty() &&
                   heights[i] < heights[st.top()]) {

                int h = heights[st.top()]; st.pop();
                int w = i - st.top() - 1; // 左右边界之间的宽度
                maxArea = max(maxArea, h * w);
            }
            st.push(i);
        }
        return maxArea;
    }
};

复杂度分析

• 时间复杂度：O(n)（每个元素最多入栈出栈各一次）
• 空间复杂度：O(n)