有效括号的嵌套深度--模仿栈

0x01.问题

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

嵌套深度 depth 定义：即有效括号字符串嵌套的层数。详情参见题末**「嵌套深度」**部分。

给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串 A 和 B：

• 不相交：每个 seq[i] 只能分给 A 和 B 二者中的一个，不能既属于 A 也属于 B 。
• A 或 B 中的元素在原字符串中可以不连续。
• A.length + B.length = seq.length

请你选出 任意 这样的 A 和 B，使得 max(depth(A), depth(B)) 的可能取值最小。其中 depth(A) 表示 A 的嵌套深度，depth(B) 表示 B 的嵌套深度。

请你返回一个长度为 seq.length 的答案数组 answer，编码规则如下：

• answer[i] = 0，seq[i] 分给 A 。
• answer[i] = 1，seq[i] 分给 B 。

即便有多个满足要求的答案存在，你也只需返回其中任意 一个 。

有效括号字符串：

仅由 "(" 和 ")" 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。

下述几种情况同样属于有效括号字符串：

• 空字符串
• 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
• 嵌套，可以记作 (A)，其中 A 是有效括号字符串

嵌套深度：

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

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

例如：""，"()()"，和 "()(()())" 都是有效括号字符串，嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。

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

C++函数形式：  vector<int> maxDepthAfterSplit(string seq) 
Java：        public int[] maxDepthAfterSplit(String seq)

题目来源于Leetcode 题1111.

0x02.要点分析

题目很长，但仔细读可以发现不是很难，题目的关键点如下：

• 给定的字符串是有效括号字符串。
• 我们要做的是把这个字符串分成两个子序列，使得这两个子序列里面的最大深度最小。
• 注意：子序列可以不连续。
• 最终返回的是分成子序列的情况。

我们把问题按步骤的分析一下，我们需要知道以下几个问题：

• 如何计算嵌套深度。
• 如何能使得两个子序列里面最大的嵌套深度最小。
• 如何返回分割的子序列数组。

我们来看第一个问题： 如何计算嵌套深度？

很明显，我们在判断括号是否匹配的时候就用过类似的思路，我们可以利用栈来再次模仿括号的匹配过程，不同的是，这次是求深度，我们可以这样来求嵌套深度：

• 遇到左括号，入栈，此时的嵌套深度就是左括号的个数。
• 遇到右括号，则此时的栈高度为嵌套深度，并pop栈顶。
• 解释：此时的栈顶是与这个括号匹配的，栈以下的部分都是待匹配的，它们都在这个括号的外面，这就是嵌套了，嵌套的深度就是此时栈中左括号的个数。

然后第二个问题： 如何能使得两个子序列里面最大的嵌套深度最小？

如果是某一个的嵌套深度最小，那么好办，从0开始找，但是这里求的是两个序列里面最大的嵌套深度最小，我们可以简单的分析一下：

• 如果A序列的嵌套深度小于B序列，那么选择的是B序列，但此时要满足嵌套深度最小，很明显可以找到更小的，B再小一点，A再大一点就好了。
• 如果A序列的嵌套深度大于B序列，那么选择的是A序列，但此时要满足嵌套深度最小，很明显可以找到更小的，A再小一点，B再大一点就叫了。

综合以上两种情况，我们可以得出，满足条件的AB序列应该是：

• AB的括号数量对半分配，这就是最佳的情况，如果A小一点，B大一点，或者A大一点，B小一点，就会出现上面的情况，根据数学的反证法，这就是满足嵌套深度最小的条件了。
• 因为给出的字符串是有效的，说明括号数量一定是偶数，这时，我们只要将配对的奇数层的左括号分配给A，偶数层的左括号分配给B，就可以满足上述情况。

最后一个问题： 如何返回分割的子序列数组。

由于我们对栈的使用，仅用于计数，所以，并不需要实际的栈，只需要一个变量记录栈的高度就行了，模仿出栈匹配括号的方法，对结果数组每次存入栈的高度%2，就行了。

0x03.解决代码–C++

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int count=0;
        vector<int> result;
        for(char c:seq){
            if(c=='('){
                count++;
                result.push_back(count&1);
            }
            else{
                result.push_back(count&1);
                count--;
            }
        }
        return result;
    }
};

0x04.解决代码–Java

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int[] ans=new int[seq.length()];
        int i=0;
        for(char c:seq.toCharArray()){
            ans[i++]=(c=='(')?i&1:(i+1)&1;
        }
        return ans;
    }
}

Leetcode 4.1 每日一题打卡完毕！

心情日记：4.1愚人节快乐，继续努力！！！

ATFWUS --Writing By 2020–04-01