1111. Maximum Nesting Depth of Two Valid Parentheses Strings

题目信息

题号:

1111

难度:

Medium

主题:

有效括号串、子序列划分、嵌套深度

原题:

LeetCode 1111

重点:

每个括号必须分配给两个子序列之一;两个子序列都要保持原顺序并各自有效,目标是最小化二者最大深度

题目重述

给定一个只含括号的有效括号字符串 seq。需要把每个字符分配到子序列 A 或 B,字符在各子序列中的相对顺序保持不变,并要求 A 和 B 都是有效括号字符串。

请返回长度与 seq 相同的数组 answer:answer[i] = 0 表示字符属于 A,answer[i] = 1 表示属于 B。选择应使 max(depth(A), depth(B)) 尽可能小;存在多个最优答案时可返回任意一个。

1 <= seq.length <= 10^4,seq 只包含 ( 和 ),并保证是有效括号字符串。

自建示例

把三层嵌套分散到两个子序列:

输入:seq = "((()))"
输出:[1,0,1,1,0,1]
解释:编号为 0 的字符组成 "()",编号为 1 的字符组成 "(())",最大深度为 2;三层嵌套不可能分成两个最大深度都小于 2 的有效子序列。

最简单的有效括号串:

输入:seq = "()"
输出:[0,0]
解释:把一对括号全部分给同一子序列即可,另一个子序列为空且同样有效。