1111. Maximum Nesting Depth of Two Valid Parentheses Strings

LeetCode 原题

Given a valid parentheses string (VPS) seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length). The subsequences may not necessarily be contiguous.

For example, for the sequence 123456789, one possible split is:

• A = {1, 3, 5, 7, 9},
• B = {2, 4, 6, 8}.

This corresponds to the output [0, 1, 0, 1, 0, 1, 0, 1, 0]  where 0 indicates membership in A and 1 indicates membership in B.

Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.

Return an answer array (of length seq.length) that encodes such a choice of A and B:  answer[i] = 0 if seq[i] is part of A, else answer[i] = 1.  Note that even though multiple answers may exist, you may return any of them.

思路：我也不知道该如何描述

笔者最开始的思路是，只需要把深度均分即可，那我遍历一遍字符串，搞出最大深度，然后大于最大深度一半的拿出来不就好了吗？

可是这么做需要遍历两次。答案给出了另一种二分法，只用遍历一次：按照层数的奇偶性来分。笔者大呼巧妙，只可惜都是O(n)时间与空间复杂度，不算什么本质上的创新，不过依旧值得学习

笔者把自己写的代码贴在下面：

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> list[int]:
        dph = []
        cur_dph = 1
        for i, c in enumerate(seq):
            if c == '(':
                dph.append(cur_dph)
                cur_dph += 1
            else:
                cur_dph -= 1
                dph.append(cur_dph)
        max_dph = max(dph)
        return [int(d > max_dph//2) for d in dph]

复杂度

• 时间，空间复杂度：O(n)