来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses
题目描述:
如果字符串满足以下条件之一,则可以称之为 有效括号字符串(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
示例 3:
输入:s = "1+(2*3)/(2-1)"
输出:1
示例 4:
输入:s = "1"
输出:0
提示:
1 <= s.length <= 100
s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
题目数据保证括号表达式 s 是 有效的括号表达式
思路:
关键条件:题目数据保证括号表达式 s 是 有效的括号表达式
- 初始化maxNum = 0,用于记录最大嵌套深度.
- 遍历字符串s,如果不是"("或者")",则跳过.
- 如果是左括号,将左括号入栈,且此时栈中左括号的数量即是当前最大嵌套深度,于maxNum比较,取大值.
- 如果是右括号,将栈顶元素弹出,消掉一对合法"()".
- 遍历结束将maxNum返回即可.
代码实现:
class Solution {
public int maxDepth(String s) {
Deque<String> d = new ArrayDeque();
int len = s.length();
int maxNum = 0;
for (int i = 0; i < len; i++) {
// 不是"("或者")",直接跳过.
if (!check(s.charAt(i) + "")) continue;
if (s.charAt(i) == '(') {
// 左括号入栈
d.addLast(s.charAt(i) + "");
// 记录当前最大嵌套深度
maxNum = Math.max(maxNum, d.size());
} else if (s.charAt(i) == ')') {
// 右括号出栈,消掉一对合法"()"
d.pollLast();
}
}
return maxNum;
}
public boolean
check(String s) {
return "(".equals(s) || ")".equals(s);
}
}
思路二:
通过观察思路一的过程可以发现,其实栈容器并不是必须的,在处理的过程中只是为了获取当前嵌套深度以及遇到')'是嵌套深度减一,可以使用一个int类型替代.
代码实现:
class Solution {
public int maxDepth(String s) {
int len = s.length();
int maxNum = 0;
int count = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == '(') {
// 嵌套深度加一
count++;
// 更新当前最大嵌套深度
maxNum = maxNum > count ? maxNum : count;
} else if (s.charAt(i) == ')') {
// 嵌套深度减一,也即是消去一对"()"
count--;
}
}
return maxNum;
}
}
网友评论