Java 中括号的最大嵌套深度

括号的最大嵌套深度的概念通常在字符串解析和数学表达式求值中会遇到。它指的是给定字符串中括号嵌套的最深级别。

给定一个只包含 '(' 和 ')' 字符的字符串，我们的目标是确定嵌套括号的最大深度。遇到开括号 '(' 时，深度会增加；遇到闭括号 ')' 时，深度会减少。在这个过程中达到的最高值就是结果。

示例

示例 1

输入：字符串 s = "((3+2)*((5-1)+2))";

输出3

解释

这个表达式中有几组嵌套的括号。最大的嵌套深度在 "((5-1)+2)" 的最内层嵌套处，深度为 3。深度从 0 开始，每遇到一个开括号 '('，深度就会增加。位置 0 的第一个括号将深度增加到 1，位置 1 的第二个开括号将其增加到 2。

继续，位置 7 的第三个开括号将深度增加到 3，这是该表达式中的最高嵌套深度。当遇到闭括号 ')' 时，深度会相应地减少。遍历字符串过程中记录的最大深度是 3，这就是最终输出。

示例 2

输入：字符串 s = "(4+5)-(6/2)+(7*3)";

输出1

解释

在这种情况下，给定的表达式包含多个括号对，但它们之间没有相互嵌套。每个括号组都是独立的，深度只有 1。当我们遍历字符串时，遇到开括号 '(' 时，深度变为 1，遇到闭括号 ')' 时，深度又会回落到 0。

由于任何括号组内部都没有嵌套，所以深度永远不会超过 1。因此，答案是 1。

示例 3

输入：字符串 s = "((((1+(2))))+((((3+(4*5))))))”;

输出6

解释

深度从 0 开始，每次找到一个开括号 '(' 时都会递增。索引 0 处的第一个括号将深度增加到 1，接着索引 1 处的第二个括号将其增加到 2，索引 2 处的第三个括号将其增加到 3，索引 3 处的第四个括号将其增加到 4。

嵌套继续，索引 4 处的第五个开括号将深度增加到 5。在表达式的更远处，可以看到另一个非常深的嵌套部分 "((((3+(4*5)))))"，其中索引 14 处的另一个开括号将深度带到了 6。继续遍历，每个闭括号 ')' 都会使深度减小，但记录到的最高深度是 6，这就是输出。

方法 1：使用迭代

算法

步骤 1：声明两个 整型 变量，`maxDepth` 用于记录达到的最高深度，`currentDepth` 用于在遍历字符串时跟踪当前深度。在开始时将两个变量都初始化为零。

步骤 2：循环遍历输入 字符串 的每个字符。当遇到开括号 '(' 时，将 `currentDepth` 加一，如果 `currentDepth` 大于迄今为止找到的最高深度，则更新 `maxDepth`。

步骤 3：如果读取到闭括号 ')'，则将 `currentDepth` 减一，以表示嵌套的减少。由于括号是正确配对的，`currentDepth` 永远不会低于零。

步骤 4：继续迭代字符串，直到扫描完所有字符，并正确跟踪计算所有开括号和闭括号。

步骤 5：遍历完成后，返回 `maxDepth` 作为结果，即在输入表达式中找到的最大嵌套级别。

步骤 6：该解决方案通过基于计数器的方法，只需对字符串进行一次遍历，即可有效地计算最大嵌套深度，而无需任何额外的数据结构。

实施

输出

 
Example 1 - Maximum Depth: 3
Example 2 - Maximum Depth: 1
Example 3 - Maximum Depth: 6   

复杂度分析

时间复杂度

该算法的时间复杂度为 O(n)，因为字符串中的每个字符都只处理一次。

空间复杂度

空间复杂度为 O(1)，因为无论输入大小如何，只使用了几个整型变量。

方法 2：使用递归

算法

步骤 1：首先声明一个 递归函数，该函数逐个遍历字符串中的每个字符。保留三个变量：`currentIndex` 用于跟踪字符串中的位置，`currentDepth` 用于计算打开括号的数量，`maxDepth` 用于保存达到的最高嵌套级别。

步骤 2：如果 `currentIndex` 到达字符串末尾，则返回迄今为止看到的最高深度，因为没有进一步的处理。如果在当前索引处遇到开括号 '('，则将 `currentDepth` 加一，如果 `currentDepth` 大于之前的最大值，则更新 `maxDepth`。

步骤 3：如果找到闭括号 ')'，则将 `currentDepth` 减一，因为它表示嵌套部分的结束。对于任何不是括号的其他字符，请在不修改深度值的情况下继续到下一个索引。

步骤 4：递归地进行，直到处理完所有字符串字符。对于每次递归调用，根据需要修改深度值，并确保函数访问输入字符串的每个字符。

步骤 5：递归完成后，返回有史以来记录的最高深度，因为它是在提供的表达式中括号的最深嵌套级别。

实施

输出

 
Example 1 - Maximum Depth: 3
Example 2 - Maximum Depth: 1
Example 3 - Maximum Depth: 6   

复杂度分析

时间复杂度

此方法的时间复杂度为 O(n)，因为每个字符都被处理一次。

空间复杂度

空间复杂度为 O(n)，因为递归调用堆栈可能会随着输入的深度而增长。

方法 3：使用堆栈

算法

步骤 1：初始化一个空堆栈来存储开括号，以及一个变量来保存达到的最大深度。逐个字符地遍历输入字符串，查找开括号或闭括号。

步骤 2：如果遇到开括号 '('，则将其压入堆栈，并根据堆栈的当前大小增加最大深度。如果遇到闭括号 ')'，则从堆栈中弹出一个元素，因为它标志着嵌套部分的结束。

步骤 3：继续处理字符串，只跟踪有效的括号，并忽略所有其他字符，如数字和运算符。

步骤 4：深度随着每个嵌套括号级别的增加而增加，并在遇到闭括号时减小。

步骤 5：当整个字符串处理完毕后，将达到的最大深度作为结果返回。

实施

输出

 
Example 1 - Maximum Depth: 3
Example 2 - Maximum Depth: 1
Example 3 - Maximum Depth: 6   

复杂度分析

时间复杂度

时间复杂度为 O(n)，因为字符串中的每个字符都只处理一次。

空间复杂度

最坏情况下的空间复杂度为 O(n)，因为堆栈存储了大量嵌套的括号，但在大多数情况下，空间使用率会显著降低。