有效括号的嵌套深度 图解题解

这道题到底在问什么

输入

seq = "(()())"

输出

[0,1,1,1,1,0]

输入

本节演示 seq = "((()))(())"

输出

[0,1,0,0,1,0,0,1,1,0]

最优解：一步一步想明白

1. 3记住这句:看括号在第几层,偶数层标 0 进 A、奇数层标 1 进 B。一层隔一层地分,配对括号同层同组。后面每一帧都在套它。
2. 4开局:深度计数器 depth = 0,分组数组还全是空位。上面一排是要扫的括号串,下面这根栈每压入一个左括号就长高一层,栈高就是当前嵌套深度,也就是层号的来源。指针从第 0 个字符开始往右走。
3. 5指针移到第 0 个字符,是一个左括号。现在栈高是 0,先看清它待在第几层,再决定标 0 还是标 1。
4. 6这个左括号进栈前深度是 0,说明它待在第 0 层。第 0 层是偶数层,归 A 组,标 0。标完把它压进栈,深度长到 1。
5. 7指针移到第 1 个字符,是一个左括号。现在栈高是 1,先看清它待在第几层,再决定标 0 还是标 1。
6. 8这个左括号进栈前深度是 1,说明它待在第 1 层。第 1 层是奇数层,归 B 组,标 1。标完把它压进栈,深度长到 2。
7. 9指针移到第 2 个字符,是一个左括号。现在栈高是 2,先看清它待在第几层,再决定标 0 还是标 1。
8. 10这个左括号进栈前深度是 2,说明它待在第 2 层。第 2 层是偶数层,归 A 组,标 0。标完把它压进栈,深度长到 3。
9. 11指针移到第 3 个字符,是一个右括号。现在栈高是 3,先看清它待在第几层,再决定标 0 还是标 1。
10. 12这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 3 落到 2。它封的正是第 2 层,和当年那个左括号同一层。第 2 层是偶数层,所以跟着标 0、进 A 组。
11. 13指针移到第 4 个字符,是一个右括号。现在栈高是 2,先看清它待在第几层,再决定标 0 还是标 1。
12. 14这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 2 落到 1。它封的正是第 1 层,和当年那个左括号同一层。第 1 层是奇数层,所以跟着标 1、进 B 组。
13. 15指针移到第 5 个字符,是一个右括号。现在栈高是 1,先看清它待在第几层,再决定标 0 还是标 1。
14. 16这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 1 落到 0。它封的正是第 0 层,和当年那个左括号同一层。第 0 层是偶数层,所以跟着标 0、进 A 组。
15. 17指针移到第 6 个字符,是一个左括号。现在栈高是 0,先看清它待在第几层,再决定标 0 还是标 1。
16. 18这个左括号进栈前深度是 0,说明它待在第 0 层。第 0 层是偶数层,归 A 组,标 0。标完把它压进栈,深度长到 1。
17. 19指针移到第 7 个字符,是一个左括号。现在栈高是 1,先看清它待在第几层,再决定标 0 还是标 1。
18. 20这个左括号进栈前深度是 1,说明它待在第 1 层。第 1 层是奇数层,归 B 组,标 1。标完把它压进栈,深度长到 2。
19. 21指针移到第 8 个字符,是一个右括号。现在栈高是 2,先看清它待在第几层,再决定标 0 还是标 1。
20. 22这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 2 落到 1。它封的正是第 1 层,和当年那个左括号同一层。第 1 层是奇数层,所以跟着标 1、进 B 组。
21. 23指针移到第 9 个字符,是一个右括号。现在栈高是 1,先看清它待在第几层,再决定标 0 还是标 1。
22. 24这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 1 落到 0。它封的正是第 0 层,和当年那个左括号同一层。第 0 层是偶数层,所以跟着标 0、进 A 组。
23. 25整串扫完,栈又空了、深度回到 0,说明括号配对完整。标 0 的拼起来是 A = "(())()",标 1 的拼起来是 B = "()()",两串都仍然括号配对。原串最深 3 层,被一层隔一层劈开后,A 最深 2 层、B 最深 1 层,更深那组只有 2 层,正好是 3 层对半向上取整的最优结果。最终分组数组 [0,1,0,0,1,0,0,1,1,0]。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        ans = [0] * len(seq)
        x = 0
        for i, c in enumerate(seq):
            if c == "(":
                ans[i] = x & 1
                x += 1
            else:
                x -= 1
                ans[i] = x & 1
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = seq.size();
        vector<int> ans(n);
        for (int i = 0, x = 0; i < n; ++i) {
            if (seq[i] == '(') {
                ans[i] = x++ & 1;
            } else {
                ans[i] = --x & 1;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int n = seq.length();
        int[] ans = new int[n];
        for (int i = 0, x = 0; i < n; ++i) {
            if (seq.charAt(i) == '(') {
                ans[i] = x++ & 1;
            } else {
                ans[i] = --x & 1;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问