有效括号的嵌套 shuitang

题目

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings

有效括号字符串 定义:对于每个左括号,都能找到与之对应的右括号,反之亦然。详情参见题末「有效括号字符串」部分。

嵌套深度 depth 定义:即有效括号字符串嵌套的层数,depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。

给你一个「有效括号字符串」 seq,请你将其分成两个不相交的有效括号字符串,A 和 B,并使这两个字符串的深度最小。

不相交:每个 seq[i] 只能分给 A 和 B 二者中的一个,不能既属于 A 也属于 B 。 A 或 B 中的元素在原字符串中可以不连续。 A.length + B.length = seq.length max(depth(A), depth(B)) 的可能取值最小。 划分方案用一个长度为 seq.length 的答案数组 answer 表示,编码规则如下:

answer[i] = 0,seq[i] 分给 A 。 answer[i] = 1,seq[i] 分给 B 。 如果存在多个满足要求的答案,只需返回其中任意 一个 即可。

示例 1:

输入:seq = “(()())” 输出:[0,1,1,1,1,0] 示例 2:

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

提示:

1 <= text.size <= 10000

有效括号字符串:

仅由 “(“ 和 “)” 构成的字符串,对于每个左括号,都能找到与之对应的右括号,反之亦然。 下述几种情况同样属于有效括号字符串:

  1. 空字符串
  2. 连接,可以记作 AB(A 与 B 连接),其中 A 和 B 都是有效括号字符串
  3. 嵌套,可以记作 (A),其中 A 是有效括号字符串 嵌套深度:

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

  1. s 为空时,depth(“”) = 0
  2. s 为 A 与 B 连接时,depth(A + B) = max(depth(A), depth(B)),其中 A 和 B 都是有效括号字符串
  3. s 为嵌套情况,depth(“(“ + A + “)”) = 1 + depth(A),其中 A 是有效括号字符串

求解思路

首先,要理解一个这样的有效括号的深度是什么。直观上可以这么理解,利用一个栈,来存左括号,遇到右括号就弹出,中间经历的栈的最大长度为有效括号的深度。可以看到,这个过程实际上,’(‘ 实际上会增大深度,而遇到一个 ‘)’ 相当于减低了深度。这一思想将是后面代码的核心:

现在题目要求我们要拆分括号, 使得拆分后连个序列的最大深度最小。我们可以这样做,分别用 a, b 保留现在序列的左括号数。如果遇到左括号,就把它分配给左括号数小的那个;如果是右括号,就把它分配给左括号数大的那个。这样就可以使得二者的深度最小了,代码如下:

代码如下:

class Solution{
public:
    vector<int> maxDepthAfterSplit(string seq){
        int a = 0, b = 0;
        vector<int> ans;
        for(int i=0;i<seq.length();i++){
            if(seq[i] == '('){
                if(a>b){
                    b++;
                    ans.push_back(1);
                }else{
                    a++;
                    ans.push_back(0);
                }
            }else{
                if(a>b){
                    a--;
                    ans.push_back(0);
                }else{
                    b--;
                    ans.push_back(1);
				}
            }
        }
        return ans;
    }
    
};