LeetCode Hot 100 · 栈篇

栈这个数据结构本身简单，但面试考的是它的两类典型套路：辅助栈（用来”记住状态/同步最小值/保存上下文”）和单调栈（用来快速找”下一个更大/更小元素”）。Hot 100 里栈分类共 5 道，恰好覆盖这两条主线。

先给一个全景地图，心里有数再逐题拆：

#20 有效的括号

题意

给定一个只包含 (、)、{、}、[、] 的字符串，判断它是否是有效的：括号必须正确匹配，且嵌套顺序正确。

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

难点与易错点

1. 只处理”匹配”还不够，还要处理”栈空”。遇到右括号时，若栈已经空了（比如第一个字符就是 )），说明没有对应的左括号，必须返回 false。这是最容易漏的分支。
2. 遍历完字符串后，栈可能不为空。比如 "((("，全程没有右括号来消栈，最后必须判断 stack.isEmpty() 才能返回，否则会误判为 true。
3. 压入”期望的右括号”比压左括号更好写。朴素做法是压左括号、遇到右括号时再去查映射表匹配；更巧的做法是遇到左括号时直接压入它对应的右括号，遇到右括号时只需 stack.peek() == c 判断即可，省掉一张 Map，也避免了 {[}] 这种”类型交叉”的坑。
4. 长度奇偶的小优化：奇数长度的字符串一定不可能完全配对，可以提前 return false（非必须，但面试里提一句是加分项）。

解法一：暴力 / 直观（消除法）

直观思路：有效的括号串，反复删掉相邻的匹配括号对（()、[]、{}），最终一定能删成空串；否则不合法。

class Solution {
    public boolean isValid(String s) {
        // 优化：长度为奇数一定不合法
        if (s.length() % 2 != 0) return false;

        StringBuilder sb = new StringBuilder(s);
        boolean changed = true;
        // 反复删除相邻的匹配括号对，直到不能再删
        while (changed && sb.length() > 0) {
            changed = false;
            for (int i = 0; i < sb.length() - 1; i++) {
                char a = sb.charAt(i), b = sb.charAt(i + 1);
                if ((a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}')) {
                    sb.delete(i, i + 2); // 删除这对相邻括号
                    changed = true;
                    break; // 删完重扫，保证嵌套结构也能被逐步消掉
                }
            }
        }
        return sb.length() == 0;
    }
}

• 时间复杂度：最坏情况下要删除 n/2 对括号，每删除一对都要从头扫一遍字符串，扫描本身是 O(n)，所以最坏 O(n²)。
• 空间复杂度：O(n)（StringBuilder 的额外空间）。
• 瓶颈在哪：每删一对就重扫一遍，重复劳动太多——嵌套越深，重复扫描次数越多。

解法二：优化 / 最优（辅助栈匹配）

本质是辅助栈匹配：遇到左括号将对应的右括号压栈；遇到右括号检查栈顶是否匹配，不匹配或栈空则 false；最终栈为空则 true。

现实类比：嵌套快递箱检查。每打开一个箱子（左括号）就在心里记下它需要的那款盖子（右括号）；拿到盖子时，它必须正好对应当前最内层的那个箱子，否则就装不回去。

容器选择：Deque<Character> 作为栈（ArrayDeque 比 Stack 类更高效，面试建议用 ArrayDeque）。

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            // 遇到左括号，将对应的右括号压栈（简化匹配逻辑）
            if      (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else {
                // 遇到右括号：栈空或栈顶不匹配，直接返回 false
                if (stack.isEmpty() || stack.peek() != c) return false;
                stack.pop();
            }
        }

        return stack.isEmpty(); // 栈不空说明有未匹配的左括号
    }
}

复杂度逐步推导：

• 时间复杂度：主循环遍历字符串一次，共 n 个字符；每个字符只会被 push 一次、pop 一次，栈操作是 O(1)。所以总时间 = n 次循环 × O(1) = O(n)。不会再出现暴力解里”删一对就重扫一遍”的重复。
• 空间复杂度：最坏情况下（全左括号 "((((..."）栈里要同时存 n 个字符，所以 O(n)。

多解法对比

本题数据规模下 n 可达 10⁴，O(n²) 会超时；而栈解法 O(n) 既简单又稳，故选最优解。

CodeTop 变体

这道题是括号问题的母题，字节、腾讯面试里常顺着往下追问：

• 含通配符版本：LeetCode 678「有效的括号字符串」——字符串里多了 *，可当左括号、右括号或空串，判断是否可能有效（贪心维护”未匹配左括号的可达区间”）。
• 最长有效括号：LeetCode 32（困难），返回最长的合法括号子串长度，可用栈或动态规划，是字节/腾讯高频压轴题。
• 括号生成：LeetCode 22，回溯生成所有合法括号组合。
• 删除无效括号：LeetCode 301（困难），BFS/回溯删除最少括号使串合法。

#155 最小栈

题意

设计一个栈，除了 push、pop、top 三个基本操作外，还要支持 getMin() 返回栈中最小元素，且所有操作都在 O(1) 时间内完成。

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

难点与易错点

1. getMin 必须 O(1)，而栈里元素是动态进出、最小值会随着 pop 失效——不能简单地”只存一个最小值变量”，否则 pop 掉当前最小值后，就没法快速找回”次小值”。
2. 辅助栈的同步是关键：主栈每 push 一个值，辅助栈也要同步 push 一个”到目前为止的最小值”，这样两个栈深度始终一致，pop 时同步弹出即可，不会断链。
3. 空栈边界：初始化时给辅助栈压一个哨兵 Integer.MAX_VALUE，这样第一次 push 时 Math.min(val, minStack.peek()) 不用额外判空，代码更干净。
4. 为什么用 min(val, peek()) 而不是”只在更小时才压”：两种写法都对，但”同步压 min”版本让 pop 无需判断，逻辑更简单不易错；“只压更小值”版本（配合 <=）能省一点空间，但要小心 pop 时的比对。

解法一：暴力 / 直观

push/pop/top 正常做，getMin 每次遍历整个栈找最小值。

class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();

    public MinStack() {}

    public void push(int val) { stack.push(val); }

    public void pop() { stack.pop(); }

    public int top() { return stack.peek(); }

    public int getMin() {
        int min = Integer.MAX_VALUE;
        // 遍历整个栈找最小值
        for (int v : stack) min = Math.min(min, v);
        return min;
    }
}

• 时间复杂度：push/pop/top 都是 O(1)，但 getMin 要遍历栈，O(n)。
• 空间复杂度：O(n)。
• 瓶颈在哪：getMin 是 O(n)，若面试要求”所有操作 O(1)“，这题就挂了——瓶颈正是最频繁被调用的 getMin。

解法二：优化 / 最优（辅助最小值栈同步维护）

本质是辅助最小值栈同步维护：主栈存数据，辅助栈 minStack 同步记录”当前栈的最小值”——每次 push 时把 min(新值, minStack 顶) 压入辅助栈。

现实类比：仓库管理 + 最便宜商品追踪。主货架存商品，另有小本子（minStack）每放一件商品就记下”到现在为止最便宜的价格”；取走商品时，同步撕掉小本子最后一条记录——这样本子最上面永远是当前最低价。

class MinStack {
    private Deque<Integer> stack    = new ArrayDeque<>();
    private Deque<Integer> minStack = new ArrayDeque<>();

    public MinStack() {
        minStack.push(Integer.MAX_VALUE); // 哨兵：避免 minStack 为空时的边界判断
    }

    public void push(int val) {
        stack.push(val);
        // 辅助栈同步记录当前最小值
        minStack.push(Math.min(val, minStack.peek()));
    }

    public void pop() {
        stack.pop();
        minStack.pop(); // 同步弹出，保持两栈深度一致
    }

    public int top()    { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

> **💭 思考**：为什么最小栈不能只用一个 `min` 变量，而要「主栈 + 辅助栈同步」？一步步想——暴力版的 `getMin` 每次遍历栈是 O(n)，而题目要求所有操作 O(1)。只存一个 `min` 变量的问题是：`pop` 掉当前最小值后，你没法 O(1) 找回「次小值」。于是想到「把历史最小值随栈一起存」——辅助栈和主栈同深度，每次 push 都记下「到目前为止的最小值」，pop 时同步弹出，这样栈顶永远是当前最小值，getMin 变成 O(1) peek。这个「用另一个栈同步记录状态」的辅助栈套路，是栈题的三大主线之一。

复杂度逐步推导：

• 时间复杂度：push 做 1 次 Math.min + 2 次栈操作，全是常数；pop 做 2 次栈操作，常数；top、getMin 各 1 次 peek，常数。所以每个操作都是 O(1)——这正是题目要求。
• 空间复杂度：主栈和辅助栈深度始终相同，各最多存 n 个元素，加起来 2n，仍是 O(n)。常量因子 2 在渐进意义下可忽略。

进阶优化（可提）：若想进一步省空间，可让辅助栈只在”新值 ≤ 当前最小值”时才压栈（用 <= 保证相等值连续压入、pop 时不断链），最坏仍 O(n)，但典型输入下省空间；更极端的”差值编码”甚至可以用单个栈 + 一个 min 变量实现 O(1) 额外空间。

多解法对比

面试常规写”双栈同步”版本即可，讲清楚 minStack 同步维护最小值的思路，再顺嘴提一句差值编码的 O(1) 空间优化，属于明显加分。

CodeTop 变体

• 数据结构互实现：LeetCode 232「用栈实现队列」、225「用队列实现栈」，是”栈/队列”这一串的基础变体，字节常考。
• 最大频率栈：LeetCode 895（困难），pop 返回出现频率最高的元素，本质是”辅助栈 + 按频率分层”的扩展。
• O(1) 额外空间最小栈：面试常追问”不用第二个栈，怎么在 O(1) 空间实现 getMin”——用栈内存储 val - min 的差值来编码，属于经典延伸追问。

#394 字符串解码

题意

给定编码字符串，编码规则为 k[encoded_string]，表示方括号内字符串重复 k 次；k 是正整数，且保证输入是合法的。要求返回解码后的字符串。

输入：s = "3[a2[c]]"        →  "accaccacc"
输入：s = "2[abc]3[cd]ef"   →  "abcabccdcdcdef"

难点与易错点

1. 多位数 k：k 可能是多位数字，比如 "10[a]"，不能只取单个字符，要用 currentNum = currentNum * 10 + digit 累积。
2. 遇到 [ 要”保存现场”：进入内层括号前，必须把当前已拼好的字符串和当前累积的数字压栈，然后清空这两个状态，否则内层和外层会混在一起。
3. 遇到 ] 的拼接顺序：弹出数字 k 和外层字符串 outer，把当前字符串重复 k 次后拼到 outer 后面，再把 outer 赋回当前结果。顺序反了（先重复外层）会直接出错。
4. 嵌套多层："3[a2[c]]" 里 2[c] 要先解成 cc，再作为 a 的后续拼成 acc，最后整体重复 3 次。栈天然保存了每一层的上下文，所以能用递归或显式栈处理。

解法一：暴力 / 直观（递归）

递归是这类”嵌套结构”最直观的解法：遇到数字就解析 k，遇到 [ 就递归进入内层拿到结果，遇到 ] 就返回当前层。

class Solution {
    public String decodeString(String s) {
        return dfs(s, new int[]{0}); // idx[0] 记录全局扫描位置
    }

    private String dfs(String s, int[] idx) {
        StringBuilder sb = new StringBuilder();
        int repeat = 0;
        while (idx[0] < s.length()) {
            char c = s.charAt(idx[0]++);
            if (Character.isDigit(c)) {
                repeat = repeat * 10 + (c - '0'); // 累积多位数
            } else if (c == '[') {
                String inner = dfs(s, idx); // 递归进入内层，得到内层结果
                for (int i = 0; i < repeat; i++) sb.append(inner);
                repeat = 0; // 用完归零
            } else if (c == ']') {
                return sb.toString(); // 本层结束，返回给外层
            } else {
                sb.append(c); // 普通字符直接追加
            }
        }
        return sb.toString();
    }
}

• 时间复杂度：O(L)，L 为解码后字符串的长度（每个最终输出字符都只 append 一次）。
• 空间复杂度：O(n)，n 为原始字符串长度（递归调用栈的深度最坏等于嵌套层数）。
• 瓶颈在哪：递归思路直观，但依赖隐式调用栈，嵌套极深时可能栈溢出；用迭代 + 显式栈能消除这个隐患，也是面试更常要求手写的版本。

解法二：优化 / 最优（双栈模拟）

本质是双栈模拟：numStack 存重复次数、strStack 存外层字符串、currentStr 记录当前层字符串、currentNum 记录当前待处理的数字。遇 [ 存现场并清空；遇 ] 恢复外层并拼接。

现实类比：俄罗斯套娃拆装。遇到 [ 就新开一个娃，把当前进度（数字 + 已拼好的串）记住；遇到 ] 就把当前这个娃里的内容复制 k 份，放回上一层娃，继续往下拼。

class Solution {
    public String decodeString(String s) {
        Deque<Integer>       numStack = new ArrayDeque<>();
        Deque<StringBuilder> strStack = new ArrayDeque<>();

        StringBuilder currentStr = new StringBuilder();
        int           currentNum = 0;

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                currentNum = currentNum * 10 + (c - '0'); // 处理多位数
            } else if (c == '[') {
                // 压栈保存当前状态，开始处理新的括号内容
                numStack.push(currentNum);
                strStack.push(currentStr);
                currentNum = 0;
                currentStr = new StringBuilder();
            } else if (c == ']') {
                // 弹出重复次数和外层字符串，拼接当前内容
                int          repeat = numStack.pop();
                StringBuilder outer = strStack.pop();
                for (int i = 0; i < repeat; i++) outer.append(currentStr);
                currentStr = outer;
            } else {
                currentStr.append(c); // 普通字符直接追加
            }
        }

        return currentStr.toString();
    }
}

> **💭 思考**：为什么字符串解码要用「双栈保存现场」，而不是一路硬拼？一步步想——递归很直观但怕深嵌套栈溢出，改成迭代后，核心难点是「进入内层括号前，外层的数字和已拼好的字符串会丢失」。所以看到 `k[...]` 这种**嵌套**结构，就该想到「栈保存每层上下文」：遇 `[` 把当前数字和字符串压栈、再清空；遇 `]` 弹出外层，把当前内容重复 k 次后拼回去。`numStack` + `strStack` 正是「遇到括号要现场保护」这个信号的自然落点。

复杂度逐步推导：

• 时间复杂度：外层循环遍历原字符串一次，共 n 个字符，每个字符只做 O(1) 的分支处理；而 append 操作的总次数等于最终输出字符串的长度 L（每个输出字符恰好被 append 一次，repeat 次循环只是把这些 append 摊开）。所以总时间 = O(n) + O(L) = O(L)（因为 L ≥ n）。
• 空间复杂度：numStack、strStack 在最坏嵌套深度下各存 n 层，currentStr 最长 O(L)。综合为 O(n + L)；通常按原始字符串规模记为 O(n)（忽略输出串这一”结果本身”的必然占用，栈结构本身是 O(n)）。

多解法对比

两者本质都是”用栈保存每层上下文”，迭代版把隐式调用栈换成了显式双栈，更稳、更好讲，故选最优。

CodeTop 变体

字符串解码是字节跳动的高频原题，常考的就是”多位数 + 嵌套括号”两个坑。同套路延伸：

• 基本计算器系列：LeetCode 224「基本计算器」、227「基本计算器 II」——遇到括号和运算符优先级时，同样用”栈保存上下文 / 操作数”，是本题思路的直接迁移。
• 递归下降 / 括号解析类：任何”括号嵌套 + 重复”的解析题（如 JSON 简化解析）都可以套”双栈 + 状态机”模板。

#739 每日温度

题意

给定整数数组 temperatures 表示每天温度，返回数组 answer，其中 answer[i] 表示从第 i 天起，还要过多少天才能等到更高的温度；如果之后都不会升高，则为 0。

输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]

难点与易错点

1. 栈里要存”下标”而不是”温度值”：因为答案要的是天数差 i - j。只存温度就丢掉了位置信息，无法计算等待天数。
2. 单调方向是”递减栈”：栈内从底到顶温度递减，只有当当前温度严格大于栈顶温度时才弹栈。用 > 而不是 >=——相等的温度不会让”后面有更高”成立，不能弹。
3. 最后留在栈里的元素不用单独处理：它们表示”之后没有更高温度”，而 answer 数组默认就是 0，天然满足题意，无需额外赋值。
4. 为什么弹栈时能确定答案：当前元素 i 就是栈顶 j 右侧第一个比它大的元素，所以 answer[j] = i - j 一定是对的，且每个下标只被赋值一次。

解法一：暴力 / 直观

对每一天 i，向后扫描找到第一个比它大的温度。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i; // 找到第一个更高的温度
                    break;
                }
            }
            // 没找到则保持默认 0
        }
        return answer;
    }
}

• 时间复杂度：两层循环，最坏（如严格递减数组 [5,4,3,2,1]，每个人都找不到更高温度，要扫到末尾）为 O(n²)。
• 空间复杂度：O(1)（除结果数组外）。
• 瓶颈在哪：大量重复扫描——每新来一个更高温度，之前那些比它矮、还没找到答案的”等待者”其实可以一次性全部结算，暴力却逐个重扫。

解法二：优化 / 最优（单调递减栈，索引栈）

本质是单调递减栈（索引栈）：栈中维护温度单调递减的下标，遍历时遇到比栈顶温度高的元素，不断弹出栈顶并计算等待天数。

现实类比：排队找下一个比自己高的人。从左往右，每个人站队等待；一旦来了一个更高的人，前面所有比他矮的人都同时”找到了自己的下一个更高的人”，一起出队结算。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>(); // 单调递减栈：存下标

        for (int i = 0; i < n; i++) {
            // 当前温度大于栈顶温度，弹出并填写等待天数
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int j = stack.pop();
                answer[j] = i - j; // 等待了 (i - j) 天
            }
            stack.push(i); // 当前下标入栈
        }

        return answer; // 剩余在栈中的下标，answer 默认 0（之后没有更高温度）
    }
}

> **💭 思考**：看到「找右侧第一个比自己大的元素」，为什么会想到单调栈？一步步想——暴力对每个 i 都向后扫一遍，瓶颈是「一个更高的温度出现时，之前所有还没找到答案的矮温度本该一次性结算，却逐个重扫」。想一次算清，就要维护一群「还没等到更高温度的候选」，而且它们的高度是**递减**的（否则高的早被结算了）。于是用一个栈存这些候选的下标、保持栈内温度递减：当前温度比栈顶高时，栈顶的答案就是 `i - j`，弹出继续，直到栈顶更高。这就是「单调递减栈 + 存下标」的由来——「下一个更大元素」类题目的统一模板。

复杂度逐步推导：

• 时间复杂度：外层 for 循环固定走 n 次；关键在于内层 while 循环——它每执行一次就 pop 一个下标，而每个下标最多被 push 一次、pop 一次，所以 while 的总执行次数等于总弹出次数 ≤ n。于是总时间 = 外层 n 次 + 内层总 ≤ n 次 = O(n)，而不是暴力解的 n²。
• 空间复杂度：栈最坏存 n 个下标（严格递减数组时全留在栈里），结果数组 O(n)，合计 O(n)。

多解法对比

n 可达 10⁵，O(n²) 会超时；单调栈把”每个元素入栈出栈各一次”摊到 O(n)，故选最优。

CodeTop 变体

每日温度是字节跳动的高频原题，它背后的模板叫”下一个更大元素”，一组延伸题几乎必背：

• 下一个更大元素 I：LeetCode 496，两数组版本，套同一个单调栈模板。
• 下一个更大元素 II：LeetCode 503，数组首尾相接（循环数组），把数组”复制一倍”或下标取模再套模板。
• 下一个更大元素 III：LeetCode 556，找比 n 大的最小数，本质是”下一个排列 + 下一个更大”。
• 接雨水：LeetCode 42（困难），单调栈/双指针，同样是”用单调结构维护左右边界”的延伸。

#84 柱状图中最大的矩形

题意

给定 heights 数组表示每个柱子的高度，柱宽均为 1，求柱状图中能勾勒出的最大矩形的面积。

输入：heights = [2,1,5,6,2,3]
输出：10

难点与易错点

1. 核心是”找到每根柱子的左右边界”：以某根柱子为高时，矩形能向左右扩展的最大宽度 = 右边第一根比它矮的位置 - 左边第一根比它矮的位置 - 1。
2. 为什么要加末尾 0 哨兵：遍历完数组后，栈里可能还残留着一路递增的柱子没被结算；在末尾补一个高度 0，保证它比所有柱子都矮，把栈里剩余的柱子全部逼出来完成计算。
3. 为什么要加栈底 -1 哨兵：栈底压 -1 代表”虚拟左边界”，这样即使某根柱子左侧没有更矮的柱子，宽度公式 i - stack.peek() - 1 也统一成立，不用为”栈空”单独分情况。
4. 弹出条件是 <= 而不是 <：遇到等于栈顶高度的柱子也要弹栈。相等时以谁为高、谁为宽结果一样，弹掉旧的、留新的，保证每个下标都被正确结算一次。
5. 宽度公式不能记错：弹出栈顶后，新的栈顶才是”左边第一根更矮的柱子”，所以宽 = i - stack.peek() - 1，用的是弹出后的栈顶。

解法一：暴力 / 直观（以每根柱子为高，向两侧扩展）

对每根柱子，把它当作矩形的高，向左、向右分别找到第一根比它矮的柱子，算出宽度和面积。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int height = heights[i];
            int left = i;
            while (left - 1 >= 0 && heights[left - 1] >= height) left--; // 向左扩展
            int right = i;
            while (right + 1 < n && heights[right + 1] >= height) right++; // 向右扩展
            maxArea = Math.max(maxArea, height * (right - left + 1));
        }
        return maxArea;
    }
}

• 时间复杂度：每根柱子都要左右扫描，最坏（全递增或全递减时每根柱子扫一段）为 O(n²)。
• 空间复杂度：O(1)。
• 瓶颈在哪：每根柱子独立地重复找”左边第一根更矮的”和”右边第一根更矮的”，这些边界信息其实可以用单调栈边遍历边一次性求出，暴力却重复计算。

解法二：优化 / 最优（单调递增栈）

本质是单调递增栈（计算每根柱子能扩展的最大宽度）：对每根柱子，用单调递增栈一次性找到左边第一根比它矮的柱子（左边界）和右边第一根比它矮的柱子（右边界），宽 = 右边界 - 左边界 - 1。

现实类比：书架上找最大面积的木板。以每块木板的高度为高，找到左右两侧第一块比它矮的位置作为边界，算出它能铺开的最大面积；一根比一根矮的板子像”台阶”，高板子需要等矮板子来”封顶”结算。

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 在末尾添加高度 0 的哨兵，确保所有柱子都能被弹出计算
        int n = heights.length;
        int[] h = new int[n + 1]; // 扩容一位
        System.arraycopy(heights, 0, h, 0, n);
        // h[n] = 0（默认值，作为右边界哨兵）

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1); // 栈底哨兵，表示虚拟左边界
        int maxArea = 0;

        for (int i = 0; i <= n; i++) {
            // 遇到比栈顶矮的柱子，弹出栈顶并计算以弹出柱子为高的最大矩形
            while (stack.peek() != -1 && h[i] <= h[stack.peek()]) {
                int height = h[stack.pop()];
                int width  = i - stack.peek() - 1; // 宽 = 右边界 - 左边界 - 1
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        return maxArea;
    }
}

> **💭 思考**：为什么「柱状图最大矩形」也用单调栈，而且栈是递增的？一步步想——暴力以每根柱子为高向两侧扩展，瓶颈是每根柱子都独立地重复找「左边第一根更矮的」和「右边第一根更矮的」，其实这些边界可以一次性求出来。核心是：要算以柱子 i 为高的矩形，只需要它左右两个「更矮边界」。用单调递增栈扫一遍，遇到 `h[i] <= h[栈顶]` 时，`h[i]` 正好是栈顶柱子的**右边界**，而弹出后的新栈顶是它的**左边界**——因为栈内保持递增，栈顶下方紧邻的那根正是左侧离它最近且更矮的柱子。于是弹出瞬间就能算完以该柱子为高的最大矩形，这就是「弹出即结算」的由来。

复杂度逐步推导：

• 时间复杂度：外层 for 循环固定执行 n+1 次；内层 while 每执行一次就 pop 一个下标，而每个下标只会被 push 一次、pop 一次，所以 while 的总执行次数 = 总弹出次数 ≤ n。总时间 = O(n)（外层）+ O(n)（内层总和）= O(n)。
• 空间复杂度：栈最坏存 n 个下标（全递增时一路入栈直到末尾 0 才结算），辅助数组 h 为 n+1，合计 O(n)。

为什么单调递增栈能同时确定左右边界：当 h[i] <= h[栈顶] 时，h[i] 是栈顶柱子的右边界（右边第一根更矮的），而弹出后新的栈顶是它的左边界（左边第一根更矮的）——因为栈内保持递增，栈顶下方相邻的那根柱子正是左侧离它最近且更矮的。于是弹出瞬间即可算完以该柱子为高的最大矩形。

多解法对比

n 可达 10⁵，O(n²) 超时；单调递增栈把”每根柱子入栈出栈各一次”摊成 O(n)，故选最优。

CodeTop 变体

柱状图最大矩形是”单调栈”最难也最经典的模板题，字节、腾讯的面试高频，最常见延伸：

• 最大矩形（二维版）：LeetCode 85（困难）——把二维 01 矩阵按行累积成”柱状高度”数组，每一行都跑一遍本题的单调栈取全局最大，是本题最直接的二维推广，字节/腾讯常考。
• 接雨水：LeetCode 42（困难）——同样利用”左右边界 + 单调结构”思想，可与本题对照着理解”单调栈求边界”的通用套路。
• 思路迁移：任何”以某元素为最小/最大、求它影响的区间范围”的问题（如”子数组最小值的和” LeetCode 907），都可套”单调栈定左右边界”模板。

小结

五道题两条主线，记牢两个模板即可应对绝大多数栈类面试题：

1. 辅助栈（20 / 155 / 394）：用栈”记住状态”——匹配括号、同步最小值、保存嵌套上下文。
2. 单调栈（739 / 84）：用栈维护单调性，从而在 O(n) 内求出每个元素的”下一个更大/更小元素”或”左右边界”。

单调栈的复杂度推导有一个统一口诀：每个下标最多入栈一次、出栈一次，所以内层 while 的总执行次数不超过 n，整体自然就是 O(n) 而不是 O(n²)——这是面试官最想听到的一句话。

章末提问

1. #84 为什么单调递增栈弹出的瞬间能同时确定「左右边界」？——结论：因为 h[i] 是栈顶柱子的右边界（右边第一根更矮的），而弹出后的新栈顶正是它的左边界（左边第一根更矮的），栈内递增保证了这个相邻关系，于是宽 = i - 新栈顶 - 1 一次算完。
2. #739 的 while 循环嵌套在 for 里，为什么是 O(n) 而不是 O(n²)？——结论：每个下标最多入栈一次、出栈一次，内层 while 的总执行次数等于总弹出次数 ≤ n，所以 for + while 合计仍是 O(n)。
3. #394 遇到 [ 为什么要「保存现场并清空」，遇到 ] 的拼接顺序为什么不能反？——结论：因为每层括号有独立的数字和字符串上下文，不压栈就会内外层混在一起；] 时必须先重复当前层、再拼到外层后面，若反过来先重复外层，会把外层的旧内容也重复一遍，结果错。