【栈】1111. 有效括号的嵌套深度

【栈】1111. 有效括号的嵌套深度
【栈】1111. 有效括号的嵌套深度

思路:维护一个栈 s,从左至右遍历括号字符串中的每一个字符:

如果当前字符是 (,就把 ( 压入栈中,此时这个 ( 的嵌套深度为栈的高度;

如果当前字符是 ),此时这个 ) 的嵌套深度为栈的高度,随后再从栈中弹出一个 (

下面给出了括号序列 (()(())()) 在每一个字符处的嵌套深度:

括号序列   ( ( ) ( ( ) ) ( ) )
下标编号   0 1 2 3 4 5 6 7 8 9
嵌套深度   1 2 2 2 3 3 2 2 2 1 

知道如何计算嵌套深度,问题就很简单了:只要在遍历过程中,我们保证栈内一半的括号属于序列 A,一半的括号属于序列 B,那么就能保证拆分后最大的嵌套深度最小,是当前最大嵌套深度的一半。要实现这样的对半分配,我们只需要把奇数层的 ( 分配给 A,偶数层的 ( 分配给 B 即可。对于上面的例子,我们将嵌套深度为 1 和 3 的所有括号 (()) 分配给 A,嵌套深度为 2 的所有括号 ()()() 分配给 B。

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        char[] chs = seq.toCharArray();
        int n = 0;
        int[] ans = new int[chs.length];
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] == '(') {
                n++;
                if (n % 2 != 0)
                    ans[i] = 1;
                else
                    ans[i] = 0;
            } else if (chs[i] == ')') {
                if (n % 2 != 0)
                    ans[i] = 1;
                else
                    ans[i] = 0;
                n--;
            }

        }
        return ans;
    }

    public static void main(String[] args) {
        new Solution().maxDepthAfterSplit("(()())");
    }
}
上一篇:java基础------运算符总结


下一篇:已知IP地址和子网掩码求出网络地址、广播地址、地址范围和主机数(转载https://blog.csdn.net/qq_39026548/article/details/78959089)