日期：2026年9月30日
LeetCode 題目連結：1111. Maximum Nesting Depth of Two Valid Parentheses Strings
解題想法
中等難度題目。題目先定義有效括號字串 (valid parentheses string, VPS)，符合以下三個條件的其中一個就是 VPS。
- 空字串
- 兩個相連的 VPS
- 一對括號之中包著另一個 VPS
- 空字串，深度 0。
- 兩個相連的 VPS $A, B$，取 $A, B$ 深度較大者。
- 一對括號之中包著另一個 VPS $A$，等於 $A$ 的深度加 1。
如果要讓一組括號嵌套深度最小，要盡量將深度平分到 $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;
}
