1614. 括号的最大嵌套深度

• 标签：栈、字符串
• 难度：简单

题目链接

• 1614. 括号的最大嵌套深度 - 力扣

题目大意

描述：给你一个有效括号字符串 $s$。

要求：返回该字符串 $s$ 的嵌套深度 。

说明：

• 如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：

  • 字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
  • 字符串可以写为 $AB$（$A$ 与 B 字符串连接），其中 $A$ 和 $B$ 都是有效括号字符串 。
  • 字符串可以写为 ($A$)，其中 $A$ 是一个有效括号字符串。

• 类似地，可以定义任何有效括号字符串 $s$ 的 嵌套深度 $depth(s)$：

  • depth("") = 0。
  • depth(C) = 0，其中 $C$ 是单个字符的字符串，且该字符不是 "(" 或者 ")"。
  • depth(A + B) = max(depth(A), depth(B))，其中 $A$ 和 $B$ 都是 有效括号字符串。
  • depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串。

• $1 \le s.length \le 100$。

• $s$ 由数字 $0 \sim 9$ 和字符 '+'、'-'、'*'、'/'、'('、')' 组成。

• 题目数据保证括号表达式 $s$ 是有效的括号表达式。

示例：

• 示例 1：

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

• 示例 2：

输入：s = "(1)+((2))+(((3)))"
输出：3

解题思路

思路 1：模拟

我们可以使用栈来进行模拟括号匹配。遍历字符串 $s$，如果遇到左括号，则将其入栈，如果遇到右括号，则弹出栈中的左括号，与当前右括号进行匹配。在整个过程中栈的大小的最大值，就是我们要求的 $s$ 的嵌套深度，其实也是求最大的连续左括号的数量（跳过普通字符，并且与右括号匹配后）。具体步骤如下：

1. 使用 $ans$ 记录最大的连续左括号数量，使用 $cnt$ 记录当前栈中左括号的数量。
2. 遍历字符串 $s$：
   1. 如果遇到左括号，则令 $cnt$ 加 $1$。
   2. 如果遇到右括号，则令 $cnt$ 减 $1$。
   3. 将 $cnt$ 与答案进行比较，更新最大的连续左括号数量。
3. 遍历完字符串 $s$，返回答案 $ans$。

思路 1：代码

class Solution:
    def maxDepth(self, s: str) -> int:
        ans, cnt = 0, 0
        for ch in s:
            if ch == '(':
                cnt += 1
            elif ch == ')':
                cnt -= 1
            ans = max(ans, cnt)

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为字符串 $s$ 的长度。
• 空间复杂度：$O(1)$。