題1 有效括號的嵌套深度

題解

要求劃分出使得最大嵌套深度最小的分組，我們首先得知道如何計算嵌套深度。我們可以通過棧實現括號匹配來計算：
維護一個棧 s，從左至右遍歷括號字符串中的每一個字符：
如果當前字符是 (，就把 ( 壓入棧中，此時這個 ( 的嵌套深度為棧的高度；
如果當前字符是 )，此時這個 ) 的嵌套深度為棧的高度，隨后再從棧中彈出一個 (。
例如：

括號序列 ( ( ) ( ( ) ) ( ) ) 下標編號 0 1 2 3 4 5 6 7 8 9 嵌套深度 1 2 2 2 3 3 2 2 2 1

只要在遍歷過程中，我們保證棧內一半的括號屬于序列 A，一半的括號屬于序列 B，那么就能保證拆分后最大的嵌套深度最小，是當前最大嵌套深度的一半。要實現這樣的對半分配，我們只需要把奇數層的 ( 分配給 A，偶數層的 ( 分配給 B 即可。對于上面的例子，我們將嵌套深度為 1 和 3 的所有括號 (()) 分配給 A，嵌套深度為 2 的所有括號 ()()() 分配給 B。

此外，由于在這個問題中，棧中只會存放 (，因此我們不需要維護一個真正的棧，只需要用一個變量模擬記錄棧的大小。

實現思路：用一個變量d來記錄當前深度，遇到"(“加1，遇到”)"減1，嵌套深度為奇數給A，嵌套深度為偶數給B

class Solution(object):def maxDepthAfterSplit(self, seq):""":type seq: str:rtype: List[int]"""ans = []d = 0for c in seq:if c == '(':d += 1ans.append(d % 2)if c == ')':ans.append(d % 2)d -= 1return ans

總結

以上是生活随笔為你收集整理的【LeetCode】4月1日打卡-Day17-括号匹配/嵌套深度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。