How do I solve the Maximum Nesting Depth of the Parentheses problem?

To solve this problem, use a stack-based approach where you track the number of open parentheses. Update the maximum depth each time the depth increases.

What is the time complexity of this problem?

The time complexity is O(N), where N is the length of the string, because you process each character exactly once.

Can I use a recursive approach to solve this problem?

While a recursive approach can work, a stack-based solution is more efficient and straightforward for this problem.

What is meant by the 'nesting depth' in this problem?

Nesting depth refers to how many layers of parentheses an expression is enclosed in. The maximum depth is the highest number of nested parentheses.

How can GhostInterview help me with this problem?

GhostInterview helps by providing a detailed, step-by-step approach for solving stack-based problems like this one, ensuring you avoid common mistakes and optimize your solution.

#1614

Easy

auto_awesome栈·状态

LeetCode 题解工作台

括号的最大嵌套深度

给定有效括号字符串 s ，返回 s 的嵌套深度。嵌套深度是嵌套括号的最大数量。示例 1：输入： s = "(1+(2*3)+(( 8 )/4))+1" 输出： 3 解释：数字 8 在嵌套的 3 层括号中。示例 2：输入： s = "(1)+((2))+((( 3 )))" 输出：…

字符串栈

题目描述

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

lightbulb

解题思路

方法一：遍历

我们用一个变量 $d$ 记录当前的深度，初始时 $d = 0$ 。

遍历字符串 $s$ ，当遇到左括号时，深度 $d$ 加一，同时更新答案为当前深度 $d$ 和答案的最大值。当遇到右括号时，深度 $d$ 减一。

最后返回答案即可。

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

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Check for the candidate's ability to implement a simple stack-based approach.
question_mark
Assess whether the candidate correctly manages nested depths during the traversal.
question_mark
Evaluate the candidate's understanding of time and space complexity optimizations.

warning

常见陷阱

外企场景

error
Failing to properly track the maximum depth during traversal.
error
Incorrectly managing the depth counters, such as failing to update `maxDepth` when necessary.
error
Overcomplicating the solution with unnecessary data structures when a simple stack-based approach suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider adding invalid parentheses in the string to check for error handling.
arrow_right_alt
Introduce additional operators and operands to test how the candidate manages complex expressions with nested parentheses.
arrow_right_alt
Test with edge cases such as strings with a single pair of parentheses or no parentheses at all.

help

常见问题

外企场景

继续练习

#1598 文件夹操作日志搜集器 #1653 使字符串平衡的最少删除次数 #1544 整理字符串