CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings
有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。
嵌套深度 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]
提示：
1 <= text.size <= 10000
有效括号字符串：
仅由 “(“ 和 “)” 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。 下述几种情况同样属于有效括号字符串：
- 空字符串
- 连接，可以记作 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 是有效括号字符串
求解思路
首先，要理解一个这样的有效括号的深度是什么。直观上可以这么理解，利用一个栈，来存左括号，遇到右括号就弹出，中间经历的栈的最大长度为有效括号的深度。可以看到，这个过程实际上，’(‘ 实际上会增大深度，而遇到一个 ‘)’ 相当于减低了深度。这一思想将是后面代码的核心：
现在题目要求我们要拆分括号, 使得拆分后连个序列的最大深度最小。我们可以这样做，分别用 a, b 保留现在序列的左括号数。如果遇到左括号，就把它分配给左括号数小的那个；如果是右括号，就把它分配给左括号数大的那个。这样就可以使得二者的深度最小了，代码如下：
代码如下：
class Solution{
public:
vector<int> maxDepthAfterSplit(string seq){
int a = 0, b = 0;
vector<int> ans;
for(int i=0;i<seq.length();i++){
if(seq[i] == '('){
if(a>b){
b++;
ans.push_back(1);
}else{
a++;
ans.push_back(0);
}
}else{
if(a>b){
a--;
ans.push_back(0);
}else{
b--;
ans.push_back(1);
}
}
}
return ans;
}
};