A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:

• It is the empty string, or
• It can be written as AB (A concatenated with B), where A and B are VPS's, or
• It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

• depth("") = 0
• depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's
• depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

For example,  "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length).

Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.

Return an answer array (of length seq.length) that encodes such a choice of A and B:  answer[i] = 0 if seq[i] is part of A, else answer[i] = 1.  Note that even though multiple answers may exist, you may return any of them.

Example 1:

Input: seq = "(()())" Output: [0,1,1,1,1,0]

Example 2:

Input: seq = "()(())()" Output: [0,0,0,1,1,0,1,1] 

Constraints:

• 1 <= seq.size <= 10000

有效括号的嵌套深度。题意是给一个用字符串表示的嵌套括号，请将input分成两个不相交的子序列，使得这两个子序列的嵌套深度的差值尽可能小。最后输出一个跟input一样长的数组，用0和1记录这两个子序列是怎么分的。

这个题二刷的时候完全没看懂自己写的是什么（????），我这里重新写一下。这个题的描述其实写的不是很好，我这里用一个例子帮助说明。首先，input给的一定是一个有效的括号组合；其次，题目要求的是你把他分成两个不相交的子序列，这里所谓的不相交的意思是input中任何一个左括号或者右括号不能同时出现在两个子序列中。例子，比如"( ( ) ( ) )"你可以分成"()"和"()()"，但是你不能分成这样，"( ( ) )"和"( ( ) )"。或者这样理解，input中的任何一个括号不能同时出现在两个子序列中。

这个题目要用到栈，跟20题类似，需要通过判断遍历的是左括号还是右括号来判断深度。相信如下这个例子可以把深度的定义说清楚。

维护一个栈 s，从左至右遍历括号字符串中的每一个字符：

如果当前字符是 (，就把 ( 压入栈中，此时这个 ( 的嵌套深度为栈的高度；

如果当前字符是 )，此时这个 ) 的嵌套深度为栈的高度，随后再从栈中弹出一个 (。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/solution/you-xiao-gua-hao-de-qian-tao-shen-du-by-leetcode-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

至于做这道题具体的思路，除了需要一个stack协助处理左括号和右括号的push和pop之外（右括号永远不push进stack），你还需要一个变量记录深度depth。在拿到每个字符（左/右括号）的时候，你需要判断这个字符的深度。拿到深度之后，你需要用深度depth % 2以帮助分组。这个地方用mod操作的逻辑是因为mod 2之后，结果一致的字符一定是同组的。

跑一下引用里面的这个例子，一开始深度depth = 0。前两个左括号放入stack都没什么问题；当下标到i = 2的时候，此时因为是一个右括号，所以此时可以结算了。首先我们看一下此时stack的size = 2，说明有两个左括号，也说明嵌套深度是两层（0和1）。此时从stack弹出一个元素（弹出的逻辑也只是因为当遇到右括号的时候，就可以弹出一个左括号跟他配对），弹出的时候记录一下这个弹出元素的下标（1）。此时判断一下stack的size是否能被2整除，如果能，则把left和i在结果数组的对应位置上置成1。不能被2整除的部分，自然就是0。

时间O(n)

空间O(n)

Java实现

1 class Solution { 2 public int[] maxDepthAfterSplit(String seq) { 3 if (seq == null || seq.isEmpty()) { 4 return new int[0]; 5 } 6 int[] res = new int[seq.length()]; 7 Stack<Integer> stack = new Stack<>(); 8 for (int i = 0; i < seq.length(); i++) { 9 if (seq.charAt(i) == '(') { 10 stack.push(i); 11 } else { 12 int depth = stack.size(); 13 int left = stack.pop(); 14 if (depth % 2 == 0) { 15 res[left] = 1; 16 res[i] = 1; 17 } 18 } 19 } 20 return res; 21 } 22 }

JavaScript实现

1 /** 2 * @param {string} seq 3 * @return {number[]} 4 */ 5 var maxDepthAfterSplit = function(seq) { 6 // corner case 7 if (seq == null || seq.length == 0) { 8 return [0]; 9 } 10 11 // normal case 12 let res = new Array(seq.length).fill(0); 13 let stack = []; 14 for (let i = 0; i < seq.length; i++) { 15 let c = seq.charAt(i); 16 if (c == '(') { 17 stack.push(i); 18 } else { 19 let depth = stack.length; 20 let left = stack.pop(); 21 if (depth % 2 == 0) { 22 res[left] = 1; 23 res[i] = 1; 24 } 25 } 26 } 27 return res; 28 };

不用stack的话，可以用位运算符判断每个字符的深度是否能被2整除，也能达到分组的目的。解释参见代码注释。

Java实现

1 /* 2 同一层次的括号在一起 3 例子: 4 ( ( ) ) ( ) 5 0 1 2 3 4 5 6 0,3和4,5是同一层次的括号, 这样两部分的depth都是1, 作差的绝对值为0 7 但是如果0,3和1,2放在一组, 那么这部分的depth=2, 另一部分depth=1, 两部分depth作差的绝对值为1 8 9 应该将同一层次的括号放到一起 10 同一层次的左括号的下标的奇偶性相同, 以左括号为参照, 比如0,3和4,5, 属于偶数层的括号; 1,2属于奇数层的括号 11 其实将括号分成了两大类, 奇数层次的括号, 偶数层次的括号 12 将奇数层次的括号放在一起, 将偶数层次的括号放在一起 13 */ 14 class Solution { 15 public int[] maxDepthAfterSplit(String seq) { 16 int n = seq.length(); 17 int[] arr = new int[n]; 18 for (int i = 0; i < n; i++) { 19 if (seq.charAt(i) == '(') { 20 //奇数层的左括号赋值为1, 偶数层的左括号赋值为0 21 arr[i] = i & 1; 22 } else { 23 //奇数层的右括号的索引是偶数, 需要对该变量赋值为1; 偶数层的右括号的索引是奇数, 需要对改变量赋值为0 24 arr[i] = (i - 1) & 1; 25 } 26 } 27 return arr; 28 } 29 }

相关题目

20. Valid Parentheses

678. Valid Parenthesis String

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

921. Minimum Add to Make Parentheses Valid

1541. Minimum Insertions to Balance a Parentheses String

LeetCode 题目总结