LeetCode 题解系列(1111)：有效括号的嵌套深度

题目描述:

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

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

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

1. 空字符串：””，depth=0
2. AB 型：”(())()”，depth=max(2,1)=2
3. (A) 型：”((())())”，depth=1+depth(A)=3

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

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

解法一: 结合栈深度

在判断有效括号时，是可以使用辅助栈进行判断的，如果是左括号，压入栈；如果是右括号，匹配栈顶，弹出栈顶。题面中的 depth 其实就是栈的最大深度。
那么，选出使 max(depth(A), depth(B)) 的可能取值最小，其实相当于让 A 字符串和 B 字符串的 depth 尽可能的接近。
因为 seq 对应的栈上，每个左括号都对应一个深度，而这个左括号，要么是 A 的，要么是 B 的。

即最深的位置总是出现在连续的括号嵌套位置，如(((())))中，此时要平均地分给A和B来保证深度最小，所以根据奇偶来一个给A一个给B这样分配。

所以，栈上的左括号只要按奇偶分配给A和B就可以了。

时间复杂度: O(N); 辅助空间复杂度: O(N)

public class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int[] ans = new int [seq.length()];
        int idx = 0;
        for(char c: seq.toCharArray()) {
            // 根据左括号所在位置的奇偶分配给 A 或 B
            // 对应的右括号就相当于在奇偶上漂移了一位
            ans[idx++] = c == '(' ? idx & 1 : ((idx + 1) & 1);
        }
        return ans;
    }
}