题目描述

有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。

嵌套深度 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]

样例2

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

算法

(栈) $O(n)$

• 括号序列一般会联想到用栈来解决(左括号进栈，匹配右括号后出栈)
• 这题的核心思想在于分组，需要把一个括号序列一分为二，且两个子序列的嵌套深度尽可能的接近(这样总嵌套深度就达到最小值)
• 如何做到尽可能的接近呢？可以发现$()$嵌套深度是1，$(())$嵌套深度是2，把这两个连续的左括号分到AB两组中，A：$()$：B$()$，总嵌套深度是1。如果把连续出现的左括号分到不同的组中，就可以保证两组的括号序列的嵌套深度尽可能接近。
• 如何用代码实现这个想法呢？定义一个变量表示栈的深度，也就是左括号的出现个数，如果左括号匹配到右括号，自然分成一组，如果左括号之后又是左括号，则分为不同的两组。这里需要注意的一点是：通过奇偶来保证是否为一组，需要在判断右括号时，先用深度来算出分组编号，再把左括号弹出。(这里说的栈不需要用真正的栈，只需要用一个变量来记录栈的深度即可)

Java 代码

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int[] res = new int[seq.length()];
        int d = 0;
        int idx = 0;
        for(char c : seq.toCharArray()){
            if(c == '('){
                d++;
                res[idx++] = d % 2;
            }else{
                res[idx++] = d % 2;
                d--;
            }
        }
        return res;
    }
}