题目

标题和出处

标题：有效括号的嵌套深度

出处：1111. 有效括号的嵌套深度

难度

6 级

题目描述

要求

一个字符串是有效括号字符串，当且仅当该字符串只包含 和 %22%7D#card=math&code=%5Ctexttt%7B%22%29%22%7D&id=c5t6o)，且满足下列条件之一：

• 字符串是一个空字符串；
• 字符串可以写为 （ 与 字符串连接），其中 和 都是有效括号字符串；
• 字符串可以写为 %7D#card=math&code=%5Ctexttt%7B%28A%29%7D&id=Y3m0g)，其中 是一个有效括号字符串。

对于有效括号字符串 ，其嵌套深度 %7D#card=math&code=%5Ctexttt%7Bdepth%28S%29%7D&id=ss1z0) 定义如下：

• %7D%20%3D%200#card=math&code=%5Ctexttt%7Bdepth%28%22%22%29%7D%20%3D%200&id=Kdak9)；
• %20%3D%20max(depth(A)%2C%20depth(B))%7D#card=math&code=%5Ctexttt%7Bdepth%28A%20%2B%20B%29%20%3D%20max%28depth%28A%29%2C%20depth%28B%29%29%7D&id=sgdcE)，其中 和 都是有效括号字符串；
• %22)%20%3D%201%20%2B%20depth(A)%7D#card=math&code=%5Ctexttt%7Bdepth%28%22%28%22%20%2B%20A%20%2B%20%22%29%22%29%20%3D%201%20%2B%20depth%28A%29%7D&id=M9jCJ)，其中 是一个有效括号字符串。

例如，、()%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%28%29%22%7D&id=s6iJ8) 和 (()())%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%28%28%29%28%29%29%22%7D&id=FlflB) 是有效括号字符串（嵌套深度分别是 、 和 ），(%22%7D#card=math&code=%5Ctexttt%7B%22%29%28%22%7D&id=YGdTH) 和 %22%7D#card=math&code=%5Ctexttt%7B%22%28%28%29%22%7D&id=OmYoA) 不是有效括号字符串。

给定一个有效括号字符串 ，将其分成两个不相交的子序列 和 ，使得 和 是有效括号字符串，且 。

选择任意的 和 使得 %2C%20depth(B))%7D#card=math&code=%5Ctexttt%7Bmax%28depth%28A%29%2C%20depth%28B%29%29%7D&id=Gojm5) 的值最小。

返回数组 （长度为 ），表示选择 和 的编码：如果 分给 则 ，否则 。如果存在多个满足要求的答案，只需返回其中任意一个即可。

示例

示例 1：

输入：())%22%7D#card=math&code=%5Ctexttt%7Bseq%20%3D%20%22%28%28%29%28%29%29%22%7D&id=MWG4K)
输出：

示例 2：

输入：(())()%22%7D#card=math&code=%5Ctexttt%7Bseq%20%3D%20%22%28%29%28%28%29%29%28%29%22%7D&id=T9Vgg)
输出：

数据范围

解法

思路和算法

在考虑将有效括号字符串分成两个不相交的子序列之前，首先需要考虑每个括号所在的嵌套深度。有效括号字符串中，每个左括号都有一个匹配的右括号，一对匹配的左右括号的嵌套深度相同。

为了计算每个括号所在的嵌套深度，可以使用栈存储左括号，根据栈内元素个数得到嵌套深度。从左到右遍历有效括号字符串 ，遇到左括号则将左括号入栈，遇到右括号则将栈顶的左括号出栈，表示当前的右括号和栈顶的左括号匹配。根据嵌套深度的定义，左括号和右括号的嵌套深度分别计算如下：

• 对于左括号，在入栈操作之后的栈内元素个数为左括号的嵌套深度；
• 对于右括号，在出栈操作之前的栈内元素个数为右括号的嵌套深度。

明确括号的嵌套深度的计算方法之后，回到原问题，将有效括号字符串 分成两个不相交的子序列 和 ，使得两个子序列的嵌套深度最小。只要栈内的一半括号属于子序列 ，另一半括号属于子序列 ，即可满足两个子序列的嵌套深度最小。实现方面，将奇数层的括号分给 ，将偶数层的括号分给 即可。

由于一对匹配的左右括号的嵌套深度相同，因此一对匹配的左右括号一定在同一个子序列中。由此可知，任意一个子序列中的左右括号数量一定相等，且左括号一定出现在与之匹配的右括号之前，因此两个子序列都是有效括号字符串。

由于栈内只存储左括号，因此并不需要真正维护一个栈，只需要记录遍历过程中的嵌套深度即可。

代码

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int length = seq.length();
        int[] answer = new int[length];
        int depth = 0;
        for (int i = 0; i < length; i++) {
            if (seq.charAt(i) == '(') {
                depth++;
                answer[i] = depth % 2 == 1 ? 0 : 1;
            } else {
                answer[i] = depth % 2 == 1 ? 0 : 1;
                depth--;
            }
        }
        return answer;
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=yRCg8)，其中 是字符串 的长度。需要遍历字符串 一次，每次更新嵌套深度的时间都是 #card=math&code=O%281%29&id=Ve64o)。
• 空间复杂度：#card=math&code=O%281%29&id=WD44w)。除了返回值以外，使用的空间复杂度是常数。