题目描述

一个字符串是 有效的 括号字符串，当且仅当它仅由 "(" 和 ")" 构成，并且：

• 它是一个空字符串，或者
• 它可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串，或者
• 它可以记作 (A)，其中 A 是有效括号字符串。

我们可以很简单地定义任意有效括号字符串 s 的 嵌套深度 depth(S)：

• depth("") = 0
• depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
• 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。即便有多个满足要求的答案存在，你也只需返回一个。

样例

输入：seq = "(()())"
输出：[0,1,1,1,1,0]

输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]

限制

• 1 <= seq.size <= 10000

算法

(贪心) $O(n)$

1. 我们可以通过一次遍历，求出每个位置的深度，求出最大的深度 maxd。具体过程为，我们维护一个当前左括号的数量 d，如果新遇到一个左括号，则 d++，更新当前位置的深度为 d；否则先更新当前位置的深度为 d，然后 d--。
2. 采用贪心策略，显然将深度最大的部分尽量分为两部分。于是，我们在深度小于等于 maxd 的地方划分给 A，其余的地方划分给 B，这样能保证最大的深度一定最小。

时间复杂度

• 遍历数组两次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要记录每个位置的深度，

C++ 代码

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = seq.length();

        int d = 0, maxd = 0;
        vector<int> depth(n), ans(n);
        for (int i = 0; i < n; i++) {
            if (seq[i] == '(') {
                depth[i] = ++d;
            } else {
                depth[i] = d--;
            }
            maxd = max(maxd, d);
        }

        maxd /= 2;
        for (int i = 0; i < n; i++)
            if (depth[i] <= maxd) {
                ans[i] = 0;
            } else {
                ans[i] = 1;
            }

        return ans;
    }
};