1614：括号的最大嵌套深度（1322 分）

Ian

2020-10-11 约 358 字预计阅读 1 分钟次阅读

力扣第 210 场周赛第 1 题

题目

给定 有效括号字符串 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 是 有效的括号字符串

分析

#1

用栈判断有效括号时，根据栈的长度即可得到每个括号所处的深度。最大的即是 s 的嵌套深度。

1
2
3
4
5
6
7
8
9


def maxDepth(self, s: str) -> int:
    res, stack = 0, []
    for char in s:
        if char == '(':
            stack.append(char)
            res = max(res, len(stack))
        elif char == ')':
            stack.pop()
    return res

24 ms

#2

注意到过程中其实只关心栈的长度。所以可以用一个变量来维护，而无需真正地进行栈操作。

解答

1
2
3
4
5
6


def maxDepth(self, s: str) -> int:
    res, size = 0, 0
    for char in s:
        size += 1 if char == '(' else -1 if char == ')' else 0
        res = max(res, size)
    return res

32 ms

目录

1614：括号的最大嵌套深度（1322 分）

题目

分析

#1

#2

解答