有效括号的嵌套深度

来源Leetcode第1111题有效括号的嵌套深度

有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。

嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。

有效括号字符串类型与对应的嵌套深度计算方法如下图所示：

给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，并使这两个字符串的深度最小。

• 不相交：每个 seq[i] 只能分给 A 和 B 二者中的一个，不能既属于 A 也属于 B 。
• A 或 B 中的元素在原字符串中可以不连续。
• A.length + B.length = seq.length
• 深度最小：max(depth(A), depth(B)) 的可能取值最小。

划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：

• answer[i] = 0，seq[i] 分给 A 。
• answer[i] = 1，seq[i] 分给 B 。

如果存在多个满足要求的答案，只需返回其中任意 一个 即可。

示例 1：

输入：seq = "(()())"
输出：[0,1,1,1,1,0]

---

题目没读懂，看weiwei的题解大概懂了一点，目要求我们把输入的整体有效字符串做一个重组，要求是只拆成两个部分 A 和 B ，每个字符要么分到 A 要么分到 B，分到 A 标记为 0，分到 B 标记为 1。而每个部分的字符又要保持在输入字符串中的顺序不变。因此输出是一个与原始字符串等长的整数数组，这个整数数组里只有 0 和 1。

核心思想就是：连续的 (会造成嵌套深度的增加，因此对于这种要把他们分到不同的组中。而连续的标准不仅仅是原始字符串中的左右相邻，应该还包括中间成对的 （）消除后的连续。

public int[] maxDepthAfterSplit(String seq) {
    int len = seq.length();
    if (seq == null || seq.isEmpty()) {
        return new int[0];
    }
    int[] ans = new int[len];
    char[] arr = seq.toCharArray();

    int depth = 0 ;  //模拟栈的深度
    for(int i = 0 ; i < len ; ++i){
        if(arr[i] == '('){
            depth++;  //左括号压栈
            ans[i] = depth % 2;
        }else{
            //右括号出栈
            ans[i] = depth % 2;
            depth--;
        }
    }
    return ans;
}