括号的最大嵌套深度

标签: 栈 字符串

难度: Easy

如果字符串满足以下条件之一，则可以称之为 有效括号字符串（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 是一个 有效括号字符串

例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。

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

示例 1：

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

示例 2：

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

提示：

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

Submission

运行时间: 22 ms

内存: 16.0 MB

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

Explain

该题解的思路是使用一个变量 left 来记录当前遍历到的字符串中左括号 '(' 的数量。当遇到左括号 '(' 时，left 的值增加 1；当遇到右括号 ')' 时，left 的值减少 1。同时，使用一个变量 ans 来记录遍历过程中 left 的最大值，即嵌套深度的最大值。最后返回 ans 作为结果。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxDepth(self, s: str) -> int:
        left = 0  # 记录左括号的数量
        ans = 0  # 记录嵌套深度的最大值
        for c in s:
            if c == '(':  # 遇到左括号
                left += 1  # 左括号数量加一
                ans = max(ans, left)  # 更新最大嵌套深度
            elif c == ')':  # 遇到右括号
                left -= 1  # 左括号数量减一
        return ans  # 返回最大嵌套深度

Explore

在解法中，遇到不是'('或')'的字符会被忽略，因为它们对计算括号的嵌套深度没有影响。算法只关注括号字符来决定嵌套深度。因此，其他字符不会影响left变量的值，也不会影响最大嵌套深度ans的计算。

如果输入字符串不是有效的括号序列，例如')('，该算法仍旧会尝试计算最大嵌套深度。在此例中，遇到')'时left会减少，可能变为负数，但这对ans的记录没有直接影响，因为ans只在遇到'('时更新。因此，尽管字符串无效，算法仍会输出计算到的最大深度，但这个值可能不反映任何有效的嵌套深度。

在本算法中，left变量在遇到')'时确实会减少，如果没有相应的前置'('，left可以变为负数。这种情况在算法中并没有特别处理，left变为负数仅表示右括号多于左括号。这不会影响ans的计算，因为ans只在left增加时（即遇到'('时）可能更新。因此，即使left变负，也不会对最大深度的计算结果产生直接影响，除非括号序列无效导致解释错误。

在代码中，选择在遇到'('后立即更新left的最大值（ans），是因为这时是确定增加了一个嵌套层级。更新ans在遇到'('后进行可以立即反映出当前深度的增加。如果在遇到')'后更新，不仅不能准确反映当前的最大嵌套深度（因为此时深度正在减少），而且可能会错过最大值的记录。因此，更新方式选择在嵌套深度增加时进行，可以更准确地记录最大嵌套深度。