【坚持每日一题5.11】1614. 括号的最大嵌套深度-白红宇

【坚持每日一题5.11】1614. 括号的最大嵌套深度

阅读量：706 次

发布时间：2019-03-21

本文共 825 字，大约阅读时间需要 2 分钟。

有效括号字符串（VPS）的嵌套深度是指括号字符串中括号的开启和闭合层次。有效括号字符串的深度定义如下：

空字符串的深度为0。

由单个非'('或')'字符组成的字符串的深度为0。

由AB两部分组成的字符串（A和B均为VPS）的深度为max(depth(A), depth(B))。

由"(A)"组成的字符串（A为VPS）的深度为1 + depth(A)。

下面将通过遍历字符串的方法来计算括号表达式的最大嵌套深度：

初始化两个变量max和count，分别记录当前遍历到的最大深度和当前层数。

遍历字符串的每一个字符：

如果是左括号'('，则count加1，并更新max。

如果是右括号')'，则count减1。

遍历结束后，max即为字符串的最大嵌套深度。

这种方法的时间复杂度为O(n)，其中n为字符串的长度。该算法在给定的约束条件下能够高效地计算括号表达式的最大嵌套深度。

class Solution {
    public int maxDepth(String s) {
        int max = 0;
        int count = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(') {
                count++;
                if (max < count) {
                    max = count;
                }
            } else if (s.charAt(i) == ')') {
                count--;
            }
        }
        return max;
    }
}