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

约 3 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节 快手
标签
字符串 栈

题目描述

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

image-20260928230642335

image-20260928230642336

题意分析

有效括号字符串的嵌套深度，就是扫描过程中同时尚未闭合的左括号数量的最大值。

解法：计数扫描

核心思路

[!blue]

用 depth 记录当前尚未闭合的左括号数，也就是已经读过的左括号数减去右括号数。遇到左括号，表示在当前结构内再进入一层，depth 加一；遇到右括号，表示退出一层，depth 减一。数字和运算符不改变括号层级。

best 保存扫描过程中 depth 的最大值。深度只有在读入左括号后才可能变大，所以先增加 depth，再更新 best。题目保证括号有效，只需知道同时打开了多少层，不必用栈保存每个左括号的位置。

有效字符串读完后 depth 会回到 0，答案应返回中途记录的 best；如果没有括号，两个变量始终为 0，结果也为 0。

解题步骤

  • 深度和答案从零开始。
  • 遇左括号先加一，再更新最大值。
  • 遇右括号减一，其他字符跳过。
  • 扫描结束后返回历史最大深度 best。

代码实现

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)$，只维护当前深度与历史最大值。

关键点总结

[!green]

  • 当前深度与历史最大深度含义不同。
  • 题目只要求数量，单一括号类型不需要栈中保存对象。

易错点总结

[!yellow]

  • 先更新答案再增加深度，会少算刚进入的一层。
  • 仅返回最终深度会得到零，丢掉中途峰值。

相似题目

题目 难度 关联与区别
20. 有效的括号 简单 本题输入已合法，只需累积当前括号深度并取最大值，不需要完整类型匹配验证。
856. 括号的分数 中等 括号层级影响嵌套分数，本题只提取最大层级这个结构信息。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/56254924
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！