脚撕LeetCode(1614)Easy
脚撕LeetCode(1614)Easy
题目地址：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+(23)+((8)/4))+1"
输出：3
解释：数字 8 在嵌套的 3 层括号中。
示例 2：
输入：s = "(1)+((2))+(((3)))"
输出：3
示例 3：
输入：s = "1+(23)/(2-1)"
输出：1
示例 4：
输入：s = "1"
输出：0
提示：
1 <= s.length <= 100
s 由数字 0-9 和字符 '+'、'-'、''、'/'、'('、')' 组成 题目数据保证括号表达式
s 是 有效的括号表达式这道题题目写的太复杂，其实就是一个数字被()嵌套一层就算作1，输出最大嵌套层数。
一、爆破法
这里爆破法我承认我有赌的成分，我想试一下，不行再改逻辑。首先我赌他有一个'('必然有一个')'，所以我们只要统计，遇到左括号就+1，右括号就-1即可，然后每次在-1之前，对比当前的左括号个数与max，如果大于max则替换max为当前count，否则不管
执行结果如下：
167 / 167 个通过测试用例
状态：通过
执行用时: 1 ms
内存消耗: 36.5 MB
public int maxDepthMe(String s) {
int left = 0;
int max = 0;
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '(') left++;
if(s.charAt(i) == ')') {
max = Math.max(max,left);
left--;
};
}
return max;
}只有双70，那么这里我们就要祭出评论区大佬的回答：
二、栈法
执行结果如下：
167 / 167 个通过测试用例
状态：通过
执行用时: 1 ms
内存消耗: 36.5 MB
public int maxDepth(String s) {
Stack<Character> stack = new Stack<>();
int res = 0;
int currentDepth = 0;
for (int i = 0;i < s.length();i ++) {
char a = s.charAt(i);
if (a == '(') {
stack.push(a);
currentDepth ++;
} else if (a == ')') {
stack.pop();
currentDepth --;
}
res = Math.max(res, currentDepth);
}
return res;
}很遗憾，用了栈之后，时间和内存并没有提升，大佬的做法是，入栈一个'('就count++，遇到')'就出栈一个'('并count--，每次循环都要Math.max给max值赋值。
不过，总算让我翻到一个时间100%的
三、评论区大佬法
public int maxDepth(String s) {
int max = 0;
int num = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c == '(') {
num++;
}else if(c == ')') {
num--;
}
if(num > max) {
max = num;
}
}
return max;
}看样子貌似和我的办法差不多，但是为什么我是1ms他是0ms？
我看了一下，给我的代码改变了一下
public int maxDepthMe(String s) {
int left = 0;
int max = 0;
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '(') left++;
// 这里加了else
else if(s.charAt(i) == ')') {
max = Math.max(max,left);
left--;
};
}
return max;
}果然我也0ms了，于是我想到了if-else分支语句中，还是有一些我们所忽略的细节，包括if-elseif
这次也是捡到了一些细节知识点，不亏。