Medium

题目描述

有效括号字符串 定义：仅由 “(” 和 “)” 构成的字符串，对于一个有效括号字符串（记作 VPS），满足以下条件：

  • 字符串是空字符串 “"，或者
  • 字符串可以写作 AB（A 与 B 连接），其中 A 和 B 都是 VPS，或者
  • 字符串可以写作 (A)，其中 A 是一个 VPS。

类似地，对于任何有效括号字符串 S，我们可以定义其 嵌套深度 depth(S)：

  • depth(”") = 0
  • depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 是 VPS
  • depth("(" + A + “)”) = 1 + depth(A)，其中 A 是 VPS

例如：""、"()()" 和 “()(()())” 都是 VPS（嵌套深度分别为 0、1、2），而 “)(” 和 “(()” 都不是 VPS。

给你一个 VPS 字符串 seq，请将其分成两个不相交的子序列 A 和 B，且 A 和 B 都是 VPS（A.length + B.length = seq.length）。

现在，你需要从这样的 A 和 B 中选择一对，使得 max(depth(A), depth(B)) 的可能取值最小。

返回一个答案数组（长度为 seq.length），编码一对满足要求的 A 和 B：answer[i] = 0 如果 seq[i] 是 A 的一部分，否则 answer[i] = 1。注意，即使有多个满足要求的答案存在，你也只需返回其中一个。

示例 1:

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

示例 2:

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

提示:

  • 1 <= seq.size <= 10000

解题思路

解题思路

这道题的核心是要将一个有效的括号字符串分成两个子序列，使得两个子序列的最大嵌套深度尽可能小。

关键观察：要使 max(depth(A), depth(B)) 最小，最好的策略是让两个子序列的深度尽可能平衡。

最优解法：按奇偶层分配

  • 我们可以根据当前的嵌套深度来决定括号的分配
  • 对于左括号 (：如果当前深度是偶数，分配给 A（标记为0）；如果是奇数，分配给 B（标记为1）
  • 对于右括号 )：它应该和对应的左括号在同一个子序列中

具体实现：

  1. 维护一个深度计数器 depth
  2. 遇到 ( 时，根据当前深度的奇偶性决定分配，然后深度加1
  3. 遇到 ) 时，先深度减1，然后根据当前深度的奇偶性决定分配

这种方法能保证两个子序列的深度差最多为1，达到最优解。

替代解法：简化按位置奇偶分配 更简单的实现是直接按括号在字符串中位置的奇偶性分配，这在大多数情况下也能得到很好的结果。

代码实现

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        vector<int> result(seq.length());
        int depth = 0;
        
        for (int i = 0; i < seq.length(); i++) {
            if (seq[i] == '(') {
                result[i] = depth % 2;
                depth++;
            } else {
                depth--;
                result[i] = depth % 2;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        result = []
        depth = 0
        
        for char in seq:
            if char == '(':
                result.append(depth % 2)
                depth += 1
            else:
                depth -= 1
                result.append(depth % 2)
        
        return result

public class Solution {
    public int[] MaxDepthAfterSplit(string seq) {
        int[] result = new int[seq.Length];
        int depth = 0;
        
        for (int i = 0; i < seq.Length; i++) {
            if (seq[i] == '(') {
                result[i] = depth % 2;
                depth++;
            } else {
                depth--;
                result[i] = depth % 2;
            }
        }
        
        return result;
    }
}

var maxDepthAfterSplit = function(seq) {
    const result = [];
    let depth = 0;
    
    for (let i = 0; i < seq.length; i++) {
        if (seq[i] === '(') {
            result[i] = depth % 2;
            depth++;
        } else {
            depth--;
            result[i] = depth % 2;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是字符串长度，需要遍历字符串一次
空间复杂度O(1)，除了输出数组外，只使用常量级额外空间

相关题目