leetcode1111-有效括号的嵌套深度

原题

有效括号字符串 仅由 "(" 和 ")" 构成,并符合下述几个条件之一:

  • 空字符串
  • 连接,可以记作 ABAB 连接),其中 A 和 B 都是有效括号字符串
  • 嵌套,可以记作 (A),其中 A 是有效括号字符串

类似地,我们可以定义任意有效括号字符串 s嵌套深度 depth(S)

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= text.size <= 10000

解法

思想

如果用栈模拟括号匹配,在栈中只存放左括号,当出现右括号的时候,左括号在栈中的下标(用ArrayList模拟栈)即代表了其在原字符串中的嵌套深度,那么要将深度均分,只需要每次出栈的时候将下标为奇偶的括号均分给A和B。

时间复杂度:O(n),n为字符串长度。

代码

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        List<Integer> stack = new ArrayList<>();
        char[] chars = seq.toCharArray();
        int[] ans = new int[chars.length];
        for(int i = 0;i<chars.length;i++){
            if(chars[i]=='('){
                stack.add(i);
            }else{
                ans[stack.get(stack.size()-1)] = stack.size()%2;
                ans[i] = stack.size()%2;
                stack.remove(stack.size()-1);
            }
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1111-%e6%9c%89%e6%95%88%e6%8b%ac%e5%8f%b7%e7%9a%84%e5%b5%8c%e5%a5%97%e6%b7%b1%e5%ba%a6/

发表回复

登录后才能评论