如果一个字符串仅由字符(和)组成并且满足以下条件则称为有效括号字符串VPS它是空字符串或它可以表示为ABA连接B其中A和B都是VPS或者它可以表示为(A)其中A是一个 VPS。我们可以类似地定义任何 VPSS的嵌套深度depth(S)如下depth() 0depth(A B) max(depth(A), depth(B))其中A和B都是 VPSdepth(( A )) 1 depth(A)其中A是一个 VPS。例如()()和()(()())都是 VPS嵌套深度 01 和 2并且)(和(()不是 VPS。给定一个 VPS 序列将其拆分成两个不相交的子序列A和B使得A和B都是 VPS且A.length B.length seq.length。这些子序列不一定是连续的。例如对于序列123456789一种可能的拆分是A {1, 3, 5, 7, 9}B {2, 4, 6, 8}。这对应于输出[0, 1, 0, 1, 0, 1, 0, 1, 0]其中 0 表示属于A1 表示属于B。现在选择任意这样的A和B使得max(depth(A), depth(B))的值是最小的。返回一个answer数组长度为seq.length该数组编码了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]解释本示例答案不唯一。 按此输出 A ()(), B ()(), max(depth(A), depth(B)) 1它们的深度最小。 像 [1,1,1,0,0,1,1,1]也是正确结果其中 A ()()(), B (), max(depth(A), depth(B)) 1 。提示1 seq.size 10000有效括号字符串仅由 ( 和 ) 构成的字符串对于每个左括号都能找到与之对应的右括号反之亦然。 下述几种情况同样属于有效括号字符串 1. 空字符串 2. 连接可以记作 ABA 与 B 连接其中 A 和 B 都是有效括号字符串 3. 嵌套可以记作 (A)其中 A 是有效括号字符串嵌套深度类似地我们可以定义任意有效括号字符串 s 的嵌套深度depth(S) 1. s 为空时depth() 02. s为A 与B连接时depth(A B) max(depth(A), depth(B))其中A和B都是有效括号字符串3. s 为嵌套情况depth(( A )) 1 depth(A)其中A是有效括号字符串。例如()()和 ()(()()) 都是有效括号字符串嵌套深度分别为 012而 )( 和(()都不是有效括号字符串。分析保证栈内一半的括号属于序列 A一半的括号属于序列 B就能保证拆分后最大的嵌套深度最小是当前最大嵌套深度的一半。从左至右遍历括号字符串中的每一个字符如果当前字符是 (就把 ( 压入栈中此时这个 ( 的嵌套深度为栈的高度如果当前字符是 )此时这个 ) 的嵌套深度为栈的高度随后再从栈中弹出一个 (。而由于在这个问题中栈中只会存放(因此不需要维护一个真正的栈只需要用一个变量模拟记录栈的大小代表当前深度即可。class Solution { public: vectorint maxDepthAfterSplit(string seq) { int nseq.length(),cnt1; vectorintans(n),dep(n); for(int i0;in;i) { if(seq[i]()dep[i]cnt; else dep[i]--cnt; } for(int i0;in;i) { if(dep[i]1)ans[i]1; else ans[i]0; } return ans; } };