题目大意：
有效括号的嵌套深度
有效括号字符串 仅由 “(” 和 “)” 构成，并符合下述几个条件之一：
空字符串
连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
嵌套，可以记作 (A)，其中 A 是有效括号字符串
类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：
s 为空时，depth(“”) = 0
s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
s 为嵌套情况，depth(“(” + A + “)”) = 1 + depth(A)，其中 A 是有效括号字符串
例如：””，”()()”，和 “()(()())” 都是有效括号字符串，嵌套深度分别为 0，1，2，而 “)(” 和 “(()” 都不是有效括号字符串。
给你一个有效括号字符串 seq，将其分成两个不相交的子序列 A 和 B，且 A 和 B 满足有效括号字符串的定义（注意：A.length + B.length = seq.length）。
现在，你需要从中选出 任意 一组有效括号字符串 A 和 B，使 max(depth(A), depth(B)) 的可能取值最小。
返回长度为 seq.length 答案数组 answer ，选择 A 还是 B 的编码规则是：如果 seq[i] 是 A 的一部分，那么 answer[i] = 0。否则，answer[i] = 1。即便有多个满足要求的答案存在，你也只需返回 一个。
示例 1：
输入：seq = “(()())”
输出：[0,1,1,1,1,0]
示例 2：
输入：seq = “()(())()”
输出：[0,0,0,1,1,0,1,1]
提示：
1 <= text.size <= 10000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1111
解题思路分析：
需要注意的是，这道题要求将一个字符串分成两个子序列，而不是两个子字符串。也就是说，在不改变字符相对顺序的前提下将其拆分成为两个部分，并且这两个部分还要满足都是有效括号字符串。另外要求出所有拆分可能中，拆分出的两个子序列的嵌套深度最小。
简单来思考，首先，无论如何拆分，新生成的两个子序列的嵌套深度和一定等于原字符串的嵌套深度。其次，要求 max(depth(A), depth(B)) 的可能取值最小值，那么就需要保证，子序列A和子序列B的深度差最小才可以。
比如原始字符串的嵌套深度为5层，在拆分后能够得到的最优解应该是一个为3层，另一个为两层，这样max(3, 2)=3才是最优解，除此之外，无论是拆成 max(1,4)或是 max(0,5)，都没办法小于3。
因此，这个最优的拆分方式一定是原字符串的嵌套深度对半拆分，例如5层拆为3和2，4层拆为2和2。
有了这个思路，我们只要将嵌套深度大于原字符串深度一半以上的部分作为一个子序列，剩下的部分作为另一个子序列就可大功告成。
最后，我们在考虑一下如何得知每个字符所在的嵌套深度。这里可以用到前缀和的方式解题。定义”(“为1， “)”为-1，循环一遍可得出每个位置字符对应的嵌套深度。比如：
//"((()))" 对应的嵌套深度应该为012210
int[] preSum = new int[seq.length()];
int sum = 0;
for(int i=0;i<seq.length();i++){
if(seq.charAt(i) == '('){
preSum[i] = ++sum;
}else{
preSum[i] = sum--;
}
} 完整的代码：
public int[] maxDepthAfterSplit(String seq) {
int maxLevel=0; // 记录最大嵌套深度
int[] preSum = new int[seq.length()]; // 记录每个字符对应当前的嵌套深度
int sum = 0; // 用于记录前缀和（深度和）
for(int i=0;i<seq.length();i++){ // 循环原字符串
if(seq.charAt(i) == '('){
// 如果是正括号，前缀和加一（注意先加一再赋值）
preSum[i] = ++sum;
maxLevel = Math.max(maxLevel, sum);
}else{
// 如果是反括号，前缀和减一（注意先赋值再减一）
preSum[i] = sum--;
}
}
int split = maxLevel / 2; // 最优深度分割
int[] res = new int[seq.length()]; // 定义返回结果
for(int i=0;i<seq.length();i++){
// 将大于最优分割深度的部分设置为1.其余默认为0
if(preSum[i] > split){
res[i]=1;
}
}
return res;
} 本解法用时2ms。
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1111-maximum-nesting-depth-of-two-valid-parentheses-strings解题思路分析/