括号的最大嵌套深度

记牢这套:d 记当前在第几层,mx 记见过的最深层;遇 "(" 进一层并刷新 mx,遇 ")" 退一层,其它字符跳过。下面每帧都在套它。

总览 · 两个计数器清零,从最左开扫：上面这排是 "(((1))(2))" 拆开的 10 个字符,开头三个连续的 "(" 一层层往里钻,中间夹着数字,后半截又开了一对括号。开扫前两个计数器都清零:d 记现在站在第几层,mx 记一路见过的最深层。从最左第 0 位往右扫。

读第 0 个 · "("：第 0 位是 "(",这是往里钻一层的信号。先把它看清,等下让深度加一。

进一层 · d 到 1 · mx 刷到 1：d 从 0 加到 1,表示现在站在第 1 层里。顺手拿 mx 比一下,1 比原来的 0 大,mx 也更新成 1。这位处理完变蓝,继续往右。

读第 1 个 · "("：第 1 位又是 "(",再往里钻一层。

进一层 · d 到 2 · mx 刷到 2：d 加到 2,现在站在第 2 层。mx 和它比,2 又比 1 大,mx 跟着刷成 2。

读第 2 个 · "("：第 2 位还是 "(",连着第三次往里钻,看来这串前段嵌得挺深。

进一层 · d 到 3 · mx 刷到 3：d 加到 3,这是目前钻得最深的一层。mx 拿 3 跟原来的 2 比,刷新成 3。记住这个 3,后面要看它还会不会被超过。

读第 3 个 · 数字 "1"：第 3 位是数字 1。数字不是括号,既不进层也不退层,d 和 mx 都原样不动,直接跳过它继续扫。

读第 4 个 · ")"：第 4 位是 ")",这是退出一层的信号。注意退层只动 d,不会去改 mx,见过的最深层是抹不掉的。

退一层 · d 回到 2 · mx 仍是 3：d 从 3 减到 2,退回第 2 层。mx 仍稳稳停在 3,它记的是历史最深,不跟着回落。

读第 5 个 · ")"：第 5 位又是 ")",再退一层。

退一层 · d 回到 1 · mx 仍是 3：d 从 2 减到 1,退回第 1 层。前面那三层括号到这就全退完两层了,mx 依旧是 3。

读第 6 个 · "("：第 6 位是 "(",又要往里钻一层。这里是关键看点:它会不会钻得比之前的 3 层还深?

进一层 · d 到 2 · mx 还是 3：d 从 1 加到 2,站到第 2 层。拿 2 跟 mx 的 3 比,2 没它大,mx 不动,还是 3。把这位标红提醒一下:虽然又开了括号,可没能刷新最深纪录。

读第 7 个 · 数字 "2"：第 7 位是数字 2,跟前面那个数字一样,不影响层数,扫过去就行。

读第 8 个 · ")"：第 8 位是 ")",退一层。

退一层 · d 回到 1 · mx 仍是 3：d 从 2 减到 1,退回第 1 层。mx 照旧是 3。

读第 9 个 · ")"：第 9 位是最后一个字符,还是 ")",再退一层。

退一层 · d 归 0 · mx 仍是 3：d 从 1 减到 0,所有括号都退干净了,正好回到最外层。一个合法括号串扫完 d 必然归 0,这也能反过来验证它配对没问题。

扫描完毕 · 看 mx：10 个字符全部扫过一遍,整排都变蓝了,d 也回到了 0。现在该看 mx 里存的是多少。

完成 · 答案 3 层：mx 定格在 3,这趟最深的一层就是第 2 位那个 "(" 钻进去时到的第 3 层。绿色标出来的就是创纪录的那一刻。后面虽然又开过括号,但都没超过它。答案就是 3,站得住。

边界三例:没括号时答案 0;单层 "(1)" 是 1;"(1)+((2))" 取两段里更深的第 2 层得 2。

面试重点:计数器代替栈省到 O(1)、mx 只在 "(" 处刷新、时间 O(n) 空间 O(1)。