leetcode
leetcode 1451 ~ 1500
括号的最大嵌套深度

括号的最大嵌套深度

难度:

标签:

题目描述

代码结果

运行时间: 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变量的值,也不会影响最大嵌套深度ans的计算。
🦆
如果输入的括号字符串不是有效的括号字符串(例如')('),算法如何处理?会有什么结果?
如果输入字符串不是有效的括号序列,例如')(',该算法仍旧会尝试计算最大嵌套深度。在此例中,遇到')'时left会减少,可能变为负数,但这对ans的记录没有直接影响,因为ans只在遇到'('时更新。因此,尽管字符串无效,算法仍会输出计算到的最大深度,但这个值可能不反映任何有效的嵌套深度。
🦆
在算法中,left变量在遇到')'时减少,如果left变成负数,这种情况在算法中如何处理?
在本算法中,left变量在遇到')'时确实会减少,如果没有相应的前置'(',left可以变为负数。这种情况在算法中并没有特别处理,left变为负数仅表示右括号多于左括号。这不会影响ans的计算,因为ans只在left增加时(即遇到'('时)可能更新。因此,即使left变负,也不会对最大深度的计算结果产生直接影响,除非括号序列无效导致解释错误。
🦆
代码中对于left的最大值是在遇到'('后立即更新,为什么不是在遇到')'后更新?这样更新有什么优势?
在代码中,选择在遇到'('后立即更新left的最大值(ans),是因为这时是确定增加了一个嵌套层级。更新ans在遇到'('后进行可以立即反映出当前深度的增加。如果在遇到')'后更新,不仅不能准确反映当前的最大嵌套深度(因为此时深度正在减少),而且可能会错过最大值的记录。因此,更新方式选择在嵌套深度增加时进行,可以更准确地记录最大嵌套深度。

相关问题