有效括号的嵌套深度 [Link]

Leetcode 4月每日一题合集

涉及知识点：栈

1. 题目描述

有效括号字符串定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。
嵌套深度 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 。

如果存在多个满足要求的答案，只需返回其中任意一个即可。
示例：

输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。

提示：

1 < seq.size <= 10000

2. 题解与分析

这题的思路很简单：

计算「有效括号字符串」seq的深度，然后除以2向上取整，得到分解后A和B的最大深度maxDepth。
分析「有效括号字符串」seq，将深度小于maxDepth的部分归于A，大于maxDepth的部分归于B即可。

则关键在于如何区分深度小于或大于maxDepth，此时需要维护一个栈Stack，遍历seq时：

遇到'('时，先入栈，栈Stack的深度就是当前括号的深度
遇到')'时，栈Stack的深度就是当前括号的深度，再出栈

3. 代码

本题的 Python 代码如下：

class Solution(object):

    def calcDepth(self, seq):
        St_top = 0  # init stack
        depth = 0
        for s in seq:
            if s == "(":
                St_top += 1  # push
            elif s == ")":
                St_top -= 1  # pop
            depth = max(depth, St_top)
        return depth

    def maxDepthAfterSplit(self, seq):
        """
        :type seq: str
        :rtype: List[int]
        """
        maxDepth = (self.calcDepth(seq) + 1)//2  # calc the max depth of sub seq
        St_top = 0  # init stack
        class_idx = []
        for s in seq:
            if s == "(":
                St_top += 1  # push
                class_idx.append(0 if St_top <= maxDepth else 1) # shallower=0, deeper=1
            elif s == ")":
                class_idx.append(0 if St_top <= maxDepth else 1)
                St_top -= 1  # pop
        return class_idx

← Previous Post Next Post →

有效括号的嵌套深度 [Link]

1. 题目描述

2. 题解与分析

3. 代码

CATALOG