1111. Maximum Nesting Depth of Two Valid Parentheses Strings¶
题目信息¶
- 题号:
1111
- 难度:
Medium
- 主题:
有效括号串、子序列划分、嵌套深度
- 原题:
- 重点:
每个括号必须分配给两个子序列之一;两个子序列都要保持原顺序并各自有效,目标是最小化二者最大深度
题目重述¶
给定一个只含括号的有效括号字符串 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]
解释:把一对括号全部分给同一子序列即可,另一个子序列为空且同样有效。