括号的最大嵌套深度
难度:
标签:
题目描述
代码结果
运行时间: 22 ms, 内存: 16.0 MB
/*
* 思路:
* 虽然Java Stream API不太适合这种带有状态的遍历操作,但我们可以通过流和自定义累加器来实现。
* 我们将会用一个IntStream来模拟遍历操作,并在累加器中记录当前深度和最大深度。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxDepth(String s) {
int[] result = IntStream.range(0, s.length()).map(i -> s.charAt(i)).reduce(new int[]{0, 0}, (acc, c) -> {
if (c == '(') acc[0]++;
else if (c == ')') acc[0]--;
acc[1] = Math.max(acc[1], acc[0]);
return acc;
}, (a, b) -> a);
return result[1];
}
}
解释
方法:
该题解的思路是使用一个变量 left 来记录当前遍历到的字符串中左括号 '(' 的数量。当遇到左括号 '(' 时,left 的值增加 1;当遇到右括号 ')' 时,left 的值减少 1。同时,使用一个变量 ans 来记录遍历过程中 left 的最大值,即嵌套深度的最大值。最后返回 ans 作为结果。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在解法中,如果遇到不是'('或')'的字符,应该如何处理,这些字符是否影响嵌套深度的计算?
▷🦆
如果输入的括号字符串不是有效的括号字符串(例如')('),算法如何处理?会有什么结果?
▷🦆
在算法中,left变量在遇到')'时减少,如果left变成负数,这种情况在算法中如何处理?
▷🦆
代码中对于left的最大值是在遇到'('后立即更新,为什么不是在遇到')'后更新?这样更新有什么优势?
▷