括号的最大嵌套深度

来源：力扣（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;
    }
}