1614. 括号的最大嵌套深度

🟢   🔖  栈 字符串  🔗 力扣 LeetCode

题目

Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"

Output: 3

Explanation:

Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"

Output: 3

Explanation:

Digit 3 is inside of 3 nested parentheses in the string.

Example 3:

Input: s = "()(())((()()))"

Output: 3

Constraints:

• 1 <= s.length <= 100
• s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
• It is guaranteed that parentheses expression s is a VPS.

题目大意

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

解题思路

要计算字符串 s 中嵌套括号的最大深度，可以通过遍历字符串，维护一个计数器来实现。

1. 初始化变量：

   • depth：表示当前括号嵌套的深度。
   • maxDepth：记录遍历过程中遇到的最大深度。

2. 遍历字符串：

   • 当遇到 '(' 时，当前深度 depth 增加 1，并更新 maxDepth 为当前 depth 和 maxDepth 的较大值。
   • 当遇到 ')' 时，当前深度 depth 减少 1。

3. 返回结果：

   • 遍历完成后，maxDepth 即为字符串中的最大嵌套深度。

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串的长度，需要遍历字符串一次。

• 空间复杂度：O(1)，使用了常数个变量 depth 和 maxDepth，不需要额外的空间。

代码

/**
 * @param {string} s
 * @return {number}
 */
var maxDepth = function (s) {
	let depth = 0,
		maxDepth = 0;
	for (let char of s) {
		if (char == '(') {
			depth++; // 当前深度增加
			maxDepth = Math.max(depth, maxDepth); // 更新最大深度
		} else if (char == ')') {
			depth--; // 当前深度减少
		}
	}
	return maxDepth;
};

相关题目

题号	标题	题解	标签	难度	力扣
1111	有效括号的嵌套深度		栈 字符串	🟠	🀄️ 🔗