均分最大深度

遍历seq计算最大深度maxDepth遍历seq，遇到"(",当A子序列的最大深度小于ceil(maxDepth/2)时分配给A，反之分配给B遇到")", 当A的最大深度不为0时说明A子序列还有未被匹配的"("，所以分配给A，否则分配给B class Solution { public int[] maxDepthAfterSplit(String seq) { List<Integer> ans = new ArrayList<>(); if (seq.length() == 0) return new int[]{}; // 记录当前深度 int depth = 0; // 记录最大深度 int maxDepth = 0; for (int i = 0; i < seq.length(); i++) { if (seq.charAt(i) == '(') { depth++; if (depth > maxDepth) maxDepth = depth; } else { depth--; } } int aDepth = 0; // 最大深度二分之一的上界 int mid = 1 + ((maxDepth - 1) / 2); for (int i = 0; i < seq.length(); i++) { if (seq.charAt(i) == '(') { if (aDepth < mid) { ans.add(0); aDepth++; }else { ans.add(1); } } else { // A中还有未被配对的左括号 if (aDepth > 0) { ans.add(0); aDepth--; } else { ans.add(1); } } } int[] res = new int[ans.size()]; for (int i = 0; i < res.length; i++) { res[i] = ans.get(i); } return res; } }

均分当前深度

如果A子序列的深度小于当前深度的一半，那么也肯定小于最大深度的一半

class Solution { public int[] maxDepthAfterSplit(String seq) { if (seq.length() == 0) return new int[]{}; int[] ans = new int[seq.length()]; // 记录当前深度 int depth = 0; int aDepth = 0; for (int i = 0; i < seq.length(); i++) { if (seq.charAt(i) == '(') { depth++; // 计算当前深度的一半 int mid = 1 + ((depth - 1) / 2); if (aDepth < mid) { ans[i] = 0; aDepth++; } else { ans[i] = 1; } } else { depth--; if (aDepth > 0) { ans[i] = 0; aDepth--; } else { ans[i] = 1; } } } return ans; } }

奇偶性

通过奇偶性将深度为奇数的括号与深度为偶数的括号平分

class Solution { public int[] maxDepthAfterSplit(String seq) { if (seq.length() == 0) return new int[]{}; int[] ans = new int[seq.length()]; // 记录当前深度 int depth = 0; for (int i = 0; i < seq.length(); i++) { if (seq.charAt(i) == '(') { ans[i] = ++depth % 2; } else { ans[i] = depth-- % 2; } } return ans; } }