LeetCode 解題筆記：1111. Maximum Nesting Depth of Two Valid Parentheses Strings

作者：王一哲
日期：2026年9月30日


LeetCode 題目連結：1111. Maximum Nesting Depth of Two Valid Parentheses Strings

解題想法

中等難度題目。題目先定義有效括號字串 (valid parentheses string, VPS)，符合以下三個條件的其中一個就是 VPS。

1. 空字串
2. 兩個相連的 VPS
3. 一對括號之中包著另一個 VPS

接下來定義嵌套深度 (nesting depth)，計算原則為

1. 空字串，深度 0。
2. 兩個相連的 VPS $A, B$，取 $A, B$ 深度較大者。
3. 一對括號之中包著另一個 VPS $A$，等於 $A$ 的深度加 1。

題目給一個字串 $seq$，要將 $seq$ 分成 $A, B$ 兩個子序列，子序列可以不連續，但是不能改變元素的順序，目標是找出使 $A, B$ 嵌套深度最小的分組方法。假設 $seq$ 的長度為 $n$，則答案 $ans$ 是一個長度為 $n$ 的陣列，如果 $seq$ 之中索引值為 $i$ 的元素被分到子序列 $A$，則 $ans[i] = 1$，如果被分到子序列 $B$，則 $ans[i] = 0$。答案可能有很多組，回傳其中一組即可。

如果要讓一組括號嵌套深度最小，要盡量將深度平分到 $A, B$ 兩組，例如 $(())$ 應該要把頭、尾兩個括號分給 $A$，內側的兩個括號分繪 $B$。可以定義變數 $balance$，記錄左括號數量減去右括號數量。用一個 for 迴圈依序讀取 $seq$ 的字元 $seq[i] = c$，如果 $c$ 是 $($，先將 $balance + 1$，如果 $balance$ 是奇數，則這個字元分給 $A$，$ans[i] = 1$；如果 $balance$ 是偶數，則這個字元分給 $B$，$ans[i] = 0$。雖然這樣的分組方式，對於範例測資 2 得到的答案不一樣，不過仍然是符合要求的答案。

seq = "()(())()"
輸出: [1,1,1,0,0,1,1,1]
範例的答案: [0,0,0,1,1,0,1,1]

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.41 MB, beats 27.78%.

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> list[int]:
        balance = 0  # 左括號數量 - 右括號數量
        n = len(seq)  # 長度
        ans = [0] * n  # 答案
        # 原則，A、B 分別負擔一半的嵌套深度
        for i in range(n):
            c = seq[i]
            if c == '(':  # 左括號
                balance += 1  # 嵌套深度加 1
                ans[i] = balance % 2  # 深度奇數分給 A，偶數分給 B
            else:  # 右括號
                # 先結算目前這層深度再更新 balance
                ans[i] = balance % 2
                balance -= 1
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 10.34 MB, beats 95.65%.

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = (int)seq.size(), balance = 0;  // 長度，左括號數量 - 右括號數量
        vector<int> ans (n, 0);  // 答案
        // 原則，A、B 分別負擔一半的嵌套深度
        for(int i = 0; i < n; i++) {
            char c = seq[i];
            if (c == '(') {  // 左括號
                balance++;  // 嵌套深度加 1
                ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
            } else {  // 右括號
                // 先結算目前這層深度再更新 balance
                ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
                balance--;
            }
        }
        return ans;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 13.05 MB, beats 50.00%.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maxDepthAfterSplit(char* seq, int* returnSize) {
    int n = strlen(seq), balance = 0;  // 左括號數量 - 右括號數量
    *returnSize = n;  // 指定回傳陣列的大小
    int* ans = (int*)malloc(n * sizeof(int));  // 答案
    // 原則，A、B 分別負擔一半的嵌套深度
    for(int i = 0; i < n; i++) {
        char c = seq[i];
        if (c == '(') {  // 左括號
            balance++;  // 嵌套深度加 1
            ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
        } else {  // 右括號
            // 先結算目前這層深度再更新 balance
            ans[i] = balance % 2;
            balance--;
        }
    }
    return ans;
}