LeetCode 1614. 括号的最大嵌套深度

2023-04-10 HGNULB 约 7 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1614. 括号的最大嵌套深度

题意分析

给定一个有效括号字符串 s（可能夹杂数字、运算符），求它的最大嵌套深度，即任意时刻同时处于「打开」状态的括号最多有几层。

题目已经保证输入是有效的 VPS——括号完全匹配、绝不会出现右括号先于左括号的情况。这一条把问题从「校验」降级为「统计」：不需要栈来检查配对合法性，也不需要处理不匹配的异常分支。识破这一点，这道题就从「括号栈」题变成了一道计数题。

非括号字符（数字、+、* 等）对深度没有任何影响，直接跳过即可。$s$ 长度不超过 $100$，规模不构成任何约束，但正确性的关键全在语义上。

边界要注意两处：字符串里可能一个括号都没有（如 "1+2"），此时深度为 $0$；深度的更新时机必须与「同时打开的层数」这个定义对齐——刚遇到左括号时该层已经打开，所以要在自增之后立刻记录。

解法：计数扫描

核心思路

教科书式的做法是压栈：遇到 ( 入栈、遇到 ) 出栈，全程记录栈的最大长度。但仔细想想，栈里装的是什么？全是完全相同的 (，栈本身没有携带任何区分性的信息。既然元素无差别，栈就退化成了一个计数器——只需要知道「现在有几个」，不需要知道「分别是哪几个」。这是本题从 $O(n)$ 空间降到 $O(1)$ 空间的全部理由，也是面试官真正想听的观察。

之所以能这样退化，前提正是题目保证的「输入有效」。如果允许非法输入，栈（或计数器加上负数校验）还要承担「右括号是否有对应左括号」的检查职责，那时计数器就必须额外判断是否变负。

于是维护两个变量，含义即全程的不变量：扫描到位置 $i$ 时，depth 表示此刻仍处于打开状态的括号层数（即已出现的 ( 数减去 ) 数），best 表示 depth 在 $[0, i]$ 上取到过的最大值。

更新规则是：遇到 ( 时 depth++——这一刻新的一层刚刚打开，depth 正好等于当前嵌套深度，所以必须紧接着用它更新 best；遇到 ) 时 depth--，表示最内层关闭，此时深度只会变小，不可能刷新最大值，所以不需要更新 best；其他字符一律忽略。

答案就是 best。由于有效性保证，扫描结束时 depth 必然回到 $0$，这可以作为一个免费的自检点。

解题步骤

初始化 depth = 0、best = 0。depth 从 $0$ 起是因为开始时没有任何括号打开；best 从 $0$ 起既是答案的下界，也直接覆盖了「字符串中没有括号」这个边界——循环里一次都不会更新它。

单趟从左到右扫描字符串。深度是一个随位置演化的量，必须按原顺序推进，不能排序也不能跳读。

遇到 ( 时先 depth++，再 best = max(best, depth)。顺序不能反：自增之后的 depth 才是「包含这个新括号在内」的当前层数；先记录再自增会让最大深度永远少 $1$。

遇到 ) 时只做 depth--，不更新 best。因为深度在这一刻减小，不可能产生新的最大值；多写一次 max 不会出错但纯属冗余，而若把 best 的更新写在这里而不写在左括号分支，则会把「关闭后的层数」当成深度，结果整体偏小 $1$。

其他字符不做任何处理。数字与运算符不参与嵌套结构，用 else if 而非 else 把它们排除在两个分支之外。

返回 best，而不是 depth——后者在有效输入下结束时恒为 $0$。

以 s = "(1+(2*3)+((8)/4))+1" 走一遍，只列出括号位置的状态变化：

初始 depth = 0、best = 0。
第 1 个字符 (：depth = 1，best = 1。
1、+ 跳过。
第 4 个字符 (：depth = 2，best = 2。此时打开的是最外层与 2*3 那一层。
2、*、3 跳过。
遇到 )：depth = 1，best 保持 $2$。
+ 跳过。
遇到 (：depth = 2，best 保持 $2$。
紧接着又遇到 (：depth = 3，best = 3。这是 ((8)/4) 里的内层，三层同时打开。
8 跳过；遇到 )：depth = 2；/、4 跳过；遇到 )：depth = 1。
遇到最后一个 )：depth = 0。
+、1 跳过。
返回 best = 3。扫描结束时 depth 归零，印证输入确实有效。

注意 best 只在两处被刷新（第一个 ( 和第三层的那个 (），其余的 ( 虽然也让 depth 上升，但没有超过历史峰值。这说明用 max 而不是直接赋值是必要的。

代码实现

class Solution {
    public int maxDepth(String s) {
        int depth = 0;
        int best = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                depth++;
                best = Math.max(best, depth);
            } else if (c == ')') {
                depth--;
            }
        }

        return best;
    }
}

func maxDepth(s string) int {
    depth := 0
    best := 0

    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            depth++
            if depth > best {
                best = depth
            }
        } else if s[i] == ')' {
            depth--
        }
    }

    return best
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为字符串长度。每个字符恰好被检查一次，循环体内是一次字符比较、一次自增自减和一次取最大值，全是常数操作。

空间复杂度：$O(1)$。只用了 depth 和 best 两个整型变量。相比压栈写法省掉了 $O(n)$ 的栈空间——栈里全是同一个 (，不携带任何信息，可以整体压缩成一个计数。

关键点总结

用栈之前先问：栈里的元素彼此有区别吗？如果全部相同，栈就可以退化成计数器，空间从 $O(n)$ 降到 $O(1)$。这个判断在括号类、信号匹配类问题里反复出现。

计数器能替代栈的前提是不需要校验合法性。本题由「输入保证有效」提供了这个前提；一旦要判合法，还需补上「计数不得为负」和「结束时必须为零」两条检查。

「最大值」类统计要把更新时机与量的语义严格对齐。深度只在打开括号的瞬间增长，所以峰值只可能在自增之后立刻出现，其他位置更新都是浪费或错误。

面试视角：这题本身十行代码，考的是你会不会主动做栈到计数器的退化。上来直接写计数器，并用一句「栈里全是同一个左括号，没有信息量」解释清楚，才是满分答案。面试官大概率会追问「如果不保证输入有效怎么办」——要能立刻补出：depth 减到负数时立即判非法，扫描结束时 depth != 0 也判非法。再追问「如果有多种括号呢」——那时元素有区别了，必须换回真正的栈来匹配类型。

易错点总结

先更新 best 再自增 depth：s = "(1)" 时会在 depth 还是 $0$ 时记录，返回 $0$，正确答案是 $1$。

把 best 的更新放在 ) 分支里：s = "((1))" 中第一次遇到 ) 时 depth 已减为 $1$，返回 $1$，正确答案是 $2$。

返回 depth 而不是 best：s = "(1+(2*3))" 结束时 depth 归零，返回 $0$，正确答案是 $2$。

用 else 而非 else if 处理右括号：s = "1+2" 中数字和 + 都会走进减法分支，depth 被减成 $-3$，虽然本例 best 仍是 $0$ 恰好正确，但 s = "(1+2)" 会因为中间三个字符各减一次而让后续深度全乱。

只用 best = depth 而不取最大值：s = "((1))+(2)" 中最后那个单层括号会把 best 覆盖成 $1$，返回 $1$，正确答案是 $2$。

误以为深度等于左括号总数：s = "()()()" 有三个左括号但它们从不同时打开，返回 $3$ 是错的，正确答案是 $1$。

用栈但只在出栈时记录栈的大小：s = "(())" 中出栈时栈已缩小，记录到的最大值是 $1$，正确答案是 $2$。

对字符用 s.charAt(i) == "(" 这种字符串比较（Java 中直接编译不过，其他语言里可能静默返回 false）：所有括号都被当成普通字符跳过，任意输入都返回 $0$。

best 初始化为 $1$：s = "1+2" 中没有任何括号，返回 $1$，正确答案是 $0$。

把非括号字符也计入深度：例如把 if (c != ')') 当作左括号分支，s = "1+2" 会返回 $3$，正确答案是 $0$。

相似题目

题目	难度	考察点
20. 有效的括号	简单	含三种括号，元素有区别，必须用真正的栈匹配类型，不能退化为计数器
678. 有效的括号字符串	中等	`*` 可当三种角色，需同时维护深度的上下界区间而非单一计数
32. 最长有效括号	困难	输入不保证有效，求最长合法段，需栈存下标或用左右计数双向扫描
856. 括号的分数	中等	同为遍历深度，但要按层累加权值，可用深度直接算 $2^{d}$ 的贡献
1249. 移除无效的括号	中等	需定位非法括号的具体下标并删除，计数器不够，要记录位置
1190. 反转每对括号间的子串	中等	括号界定的是操作范围，需按嵌套层维护待反转的内容
224. 基本计算器	困难	括号嵌套决定符号与运算优先级，栈里存的是上下文而非同质元素
22. 括号生成	中等	反向构造所有有效串，靠剩余左右括号数剪枝，深度约束变成生成条件