题目描述
思路解析动画文字版
记住这句:看括号在第几层,偶数层标 0 进 A、奇数层标 1 进 B。一层隔一层地分,配对括号同层同组。后面每一帧都在套它。
开局:深度计数器 depth = 0,分组数组还全是空位。上面一排是要扫的括号串,下面这根栈每压入一个左括号就长高一层,栈高就是当前嵌套深度,也就是层号的来源。指针从第 0 个字符开始往右走。
指针移到第 0 个字符,是一个左括号。现在栈高是 0,先看清它待在第几层,再决定标 0 还是标 1。
这个左括号进栈前深度是 0,说明它待在第 0 层。第 0 层是偶数层,归 A 组,标 0。标完把它压进栈,深度长到 1。
指针移到第 1 个字符,是一个左括号。现在栈高是 1,先看清它待在第几层,再决定标 0 还是标 1。
这个左括号进栈前深度是 1,说明它待在第 1 层。第 1 层是奇数层,归 B 组,标 1。标完把它压进栈,深度长到 2。
指针移到第 2 个字符,是一个左括号。现在栈高是 2,先看清它待在第几层,再决定标 0 还是标 1。
这个左括号进栈前深度是 2,说明它待在第 2 层。第 2 层是偶数层,归 A 组,标 0。标完把它压进栈,深度长到 3。
指针移到第 3 个字符,是一个右括号。现在栈高是 3,先看清它待在第几层,再决定标 0 还是标 1。
这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 3 落到 2。它封的正是第 2 层,和当年那个左括号同一层。第 2 层是偶数层,所以跟着标 0、进 A 组。
指针移到第 4 个字符,是一个右括号。现在栈高是 2,先看清它待在第几层,再决定标 0 还是标 1。
这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 2 落到 1。它封的正是第 1 层,和当年那个左括号同一层。第 1 层是奇数层,所以跟着标 1、进 B 组。
指针移到第 5 个字符,是一个右括号。现在栈高是 1,先看清它待在第几层,再决定标 0 还是标 1。
这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 1 落到 0。它封的正是第 0 层,和当年那个左括号同一层。第 0 层是偶数层,所以跟着标 0、进 A 组。
指针移到第 6 个字符,是一个左括号。现在栈高是 0,先看清它待在第几层,再决定标 0 还是标 1。
这个左括号进栈前深度是 0,说明它待在第 0 层。第 0 层是偶数层,归 A 组,标 0。标完把它压进栈,深度长到 1。
指针移到第 7 个字符,是一个左括号。现在栈高是 1,先看清它待在第几层,再决定标 0 还是标 1。
这个左括号进栈前深度是 1,说明它待在第 1 层。第 1 层是奇数层,归 B 组,标 1。标完把它压进栈,深度长到 2。
指针移到第 8 个字符,是一个右括号。现在栈高是 2,先看清它待在第几层,再决定标 0 还是标 1。
这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 2 落到 1。它封的正是第 1 层,和当年那个左括号同一层。第 1 层是奇数层,所以跟着标 1、进 B 组。
指针移到第 9 个字符,是一个右括号。现在栈高是 1,先看清它待在第几层,再决定标 0 还是标 1。
这个右括号先弹掉栈顶,把它配对的那个左括号送走,深度从 1 落到 0。它封的正是第 0 层,和当年那个左括号同一层。第 0 层是偶数层,所以跟着标 0、进 A 组。
整串扫完,栈又空了、深度回到 0,说明括号配对完整。标 0 的拼起来是 A = "(())()",标 1 的拼起来是 B = "()()",两串都仍然括号配对。原串最深 3 层,被一层隔一层劈开后,A 最深 2 层、B 最深 1 层,更深那组只有 2 层,正好是 3 层对半向上取整的最优结果。最终分组数组 [0,1,0,0,1,0,0,1,1,0]。
边界都一个套路:只看每个括号在第几层,偶数层标 0、奇数层标 1,配对的一左一右总是同层同组。
面试重点:交替分组达到 ceil(D/2) 的下界即最优;深度计数是一类括号题的共同母题。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n)，n 为括号串长度。每个字符只看一遍,算一次层号奇偶就定下它的组,整体是线性扫描
- 空间：O(1)，只需一个整数深度计数器;真实代码连栈都不用开。返回的分组数组是题目要求的输出,不计入额外空间
易错点
面试追问把动画讲成自己的话
追问为什么按层号奇偶交替分组,就能让更深那组的深度最小?
追问这题和判断有效括号(lc20)、删最外层括号(lc1021)是什么关系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
反转每对括号间的子串
LeetCode 1190 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题