Easy

题目描述

给你一个有效的括号字符串 s，返回该字符串的 s 的嵌套深度。嵌套深度是最大的嵌套括号数。

示例 1：

输入：s = "(1+(2*3)+((8)/4))+1"
输出：3
解释：数字 8 在 3 层嵌套括号中。

示例 2：

输入：s = "(1)+((2))+(((3)))"
输出：3
解释：数字 3 在 3 层嵌套括号中。

示例 3：

输入：s = "()(())((()()))"
输出：3

提示：

  • 1 <= s.length <= 100
  • s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
  • 题目数据保证括号表达式 s 是 有效的括号表达式

提示：

  • 有效括号表达式 (VPS) 中任意字符的深度 = 它前面的左括号数 - 它前面的右括号数

解题思路

解题思路

这道题要求找到括号的最大嵌套深度。对于一个有效的括号表达式，嵌套深度就是在任意位置同时"打开"的左括号的最大数量。

核心思路：

  1. 遍历字符串，使用一个计数器记录当前的嵌套层数
  2. 遇到左括号 ( 时，层数加1
  3. 遇到右括号 ) 时，层数减1
  4. 在遍历过程中记录层数的最大值

算法步骤：

  • 初始化当前深度 current_depth = 0 和最大深度 max_depth = 0
  • 遍历字符串中的每个字符：
    • 如果是左括号，当前深度加1，同时更新最大深度
    • 如果是右括号，当前深度减1
    • 其他字符忽略
  • 返回最大深度

这个方法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常高效。由于题目保证输入是有效的括号表达式，所以不需要额外的括号匹配检查。

推荐解法： 单次遍历 + 计数器法，简洁高效。

代码实现

class Solution {
public:
    int maxDepth(string s) {
        int currentDepth = 0;
        int maxDepth = 0;
        
        for (char c : s) {
            if (c == '(') {
                currentDepth++;
                maxDepth = max(maxDepth, currentDepth);
            } else if (c == ')') {
                currentDepth--;
            }
        }
        
        return maxDepth;
    }
};

class Solution:
    def maxDepth(self, s: str) -> int:
        current_depth = 0
        max_depth = 0
        
        for c in s:
            if c == '(':
                current_depth += 1
                max_depth = max(max_depth, current_depth)
            elif c == ')':
                current_depth -= 1
        
        return max_depth

public class Solution {
    public int MaxDepth(string s) {
        int currentDepth = 0;
        int maxDepth = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                currentDepth++;
                maxDepth = Math.Max(maxDepth, currentDepth);
            } else if (c == ')') {
                currentDepth--;
            }
        }
        
        return maxDepth;
    }
}

var maxDepth = function(s) {
    let depth = 0;
    let maxDepth = 0;
    
    for (let char of s) {
        if (char === '(') {
            depth++;
            maxDepth = Math.max(maxDepth, depth);
        } else if (char === ')') {
            depth--;
        }
    }
    
    return maxDepth;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，n 为字符串长度
空间复杂度O(1)只使用常数个变量存储当前深度和最大深度

相关题目