括号的最大嵌套深度 图解题解
这道题到底在问什么
- 输入
- s = "(1)"
- 输出
- 1
- 输入
- s = "((1))"
- 输出
- 2
- 输入
- 本节演示 s = "(((1))(2))"
- 输出
- 3
最优解：一步一步想明白
- 3记牢这套:d 记当前在第几层,mx 记见过的最深层;遇 "(" 进一层并刷新 mx,遇 ")" 退一层,其它字符跳过。下面每帧都在套它。
- 4上面这排是 "(((1))(2))" 拆开的 10 个字符,开头三个连续的 "(" 一层层往里钻,中间夹着数字,后半截又开了一对括号。开扫前两个计数器都清零:d 记现在站在第几层,mx 记一路见过的最深层。从最左第 0 位往右扫。
- 5第 0 位是 "(",这是往里钻一层的信号。先把它看清,等下让深度加一。
- 6d 从 0 加到 1,表示现在站在第 1 层里。顺手拿 mx 比一下,1 比原来的 0 大,mx 也更新成 1。这位处理完变蓝,继续往右。
- 7第 1 位又是 "(",再往里钻一层。
- 8d 加到 2,现在站在第 2 层。mx 和它比,2 又比 1 大,mx 跟着刷成 2。
- 9第 2 位还是 "(",连着第三次往里钻,看来这串前段嵌得挺深。
- 10d 加到 3,这是目前钻得最深的一层。mx 拿 3 跟原来的 2 比,刷新成 3。记住这个 3,后面要看它还会不会被超过。
- 11第 3 位是数字 1。数字不是括号,既不进层也不退层,d 和 mx 都原样不动,直接跳过它继续扫。
- 12第 4 位是 ")",这是退出一层的信号。注意退层只动 d,不会去改 mx,见过的最深层是抹不掉的。
- 13d 从 3 减到 2,退回第 2 层。mx 仍稳稳停在 3,它记的是历史最深,不跟着回落。
- 14第 5 位又是 ")",再退一层。
- 15d 从 2 减到 1,退回第 1 层。前面那三层括号到这就全退完两层了,mx 依旧是 3。
- 16第 6 位是 "(",又要往里钻一层。这里是关键看点:它会不会钻得比之前的 3 层还深?
- 17d 从 1 加到 2,站到第 2 层。拿 2 跟 mx 的 3 比,2 没它大,mx 不动,还是 3。把这位标红提醒一下:虽然又开了括号,可没能刷新最深纪录。
- 18第 7 位是数字 2,跟前面那个数字一样,不影响层数,扫过去就行。
- 19第 8 位是 ")",退一层。
- 20d 从 2 减到 1,退回第 1 层。mx 照旧是 3。
- 21第 9 位是最后一个字符,还是 ")",再退一层。
- 22d 从 1 减到 0,所有括号都退干净了,正好回到最外层。一个合法括号串扫完 d 必然归 0,这也能反过来验证它配对没问题。
- 2310 个字符全部扫过一遍,整排都变蓝了,d 也回到了 0。现在该看 mx 里存的是多少。
- 24mx 定格在 3,这趟最深的一层就是第 2 位那个 "(" 钻进去时到的第 3 层。绿色标出来的就是创纪录的那一刻。后面虽然又开过括号,但都没超过它。答案就是 3,站得住。
⚠️ 容易写错的地方
✗ 错：老老实实建一个栈,遇 "(" 压进去、遇 ")" 弹出来,再看栈最大高度
✓ 对：其实只要一个深度计数器 d 就够,遇 "(" 加一、遇 ")" 减一
栈里压的全是 "(",真正有用的只是它的高度。用一个整数记高度就行,空间从 O(n) 直接降到 O(1),省一个栈
✗ 错：扫完才去看 d 当成答案
✓ 对：必须在每次 "(" 之后就用 max 把 d 记进 ans
合法括号串扫到末尾 d 一定归 0,真正的最深值出现在扫描途中。不在途中记峰值,最后只会得到 0
✗ 错：把数字和加减乘除也当回事,试着给它们算层数
✓ 对：只有 "(" 和 ")" 改变深度,其它字符一律跳过
题目里数字和运算符只是干扰项,既不进层也不退层。误把它们纳入判断,逻辑会绕乱甚至数错
完整代码（Python / C++ / Java）
Python
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 maxDepth(self, s: str) -> int:
ans = d = 0
for c in s:
if c == '(':
d += 1
ans = max(ans, d)
elif c == ')':
d -= 1
return ansC++
#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:
int maxDepth(string s) {
int ans = 0, d = 0;
for (char& c : s) {
if (c == '(') {
ans = max(ans, ++d);
} else if (c == ')') {
--d;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxDepth(String s) {
int ans = 0, d = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == '(') {
ans = Math.max(ans, ++d);
} else if (c == ')') {
--d;
}
}
return ans;
}
}复杂度
时间
O(n)
n 为字符串长度。每个字符只看一遍,做常数次判断和加减,整体是一遍线性扫描
空间
O(1)
自始至终只用 d 和 ans 两个整数,没有真去建栈或开数组,峰值占用是常数,跟串多长、嵌多深都无关
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 括号的最大嵌套深度 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么用一个计数器就行,不必真的开一个栈?+
括号匹配确实常用栈,但这题只关心嵌套有多深,而栈里压的全是相同的 "(",真正有意义的只是栈的高度。既然如此,用一个整数 d 记高度就够了:遇 "(" 加一、遇 ")" 减一,再用 mx 记途中峰值。空间从 O(n) 降到 O(1),还省掉了建栈的开销。
mx 为什么只在遇到 "(" 的时候刷新,遇 ")" 不刷?+
深度只会在进层那一刻达到一个新高,也就是 "(" 让 d 加一之后。退层时 d 在减小,不可能产生更深的层,自然不用刷 mx。所以把 max 这步只放在 "(" 分支里,既正确又少做无用功。
这题的时间和空间复杂度是多少?+
时间 O(n),n 是串长,每个字符只看一遍,做常数次判断和加减。空间 O(1),全程只有 d 和 ans 两个整数在动,不开数组也不建栈。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 括号的最大嵌套深度 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。