1.題目

原題：

給定一個(gè)只包含 '(' 和 ')' 的字符串，找出最長的包含有效括號(hào)的子串的長度。

例子：

輸入: "(()"
輸出: 2
解釋: 最長有效括號(hào)子串為 "()"

2.解析

這道題可以好好盤一盤我的心路歷程，里邊全是坑，大家注意避著點(diǎn)。
先來說正確解法：棧和動(dòng)態(tài)規(guī)劃。
棧是這次考慮的重點(diǎn)，動(dòng)態(tài)規(guī)劃以后有空再補(bǔ)充。

2.1 我的錯(cuò)誤做法

當(dāng)時(shí)我思考的棧解決問題，但是我考慮的太復(fù)雜了，甚至加了雙指針。

• 疑點(diǎn)1，為啥不用雙指針
  答：棧本來就是動(dòng)態(tài)的，可以不斷地入棧、出棧，本來就可以記錄下標(biāo)位置。
• 疑點(diǎn)2，用for循環(huán)還是while循環(huán)
  答：其實(shí)都可以，for循環(huán)和while循環(huán)一層就可以了，不用考慮正確匹配的開始位置可能是第一個(gè)也能是第n個(gè)，因?yàn)闂？梢杂涗浵滤蟹蠗l件的括號(hào)集合。
• 疑點(diǎn)3，什么時(shí)候進(jìn)行有效括號(hào)的計(jì)算
  答：遇到左括號(hào)就入棧，這個(gè)是肯定的，因?yàn)橹灰亲罄ㄌ?hào)，就可能有有效匹配，因此計(jì)算只能出在右括號(hào)里。
  右括號(hào)也分情況：
• 第一種是?？樟耍⒁膺@個(gè)?？樟说囊馑际菦]有左括號(hào)可以和這個(gè)右括號(hào)匹配，這個(gè)時(shí)候觀察一下，i - start和當(dāng)前最大有效括號(hào)lk（下面簡稱lk了）之間的最大值就是此次的lk。
  這里的小疑點(diǎn)，為啥是i- start？因?yàn)橛行У钠ヅ湮恢檬莍-1，思考一下這個(gè)）括號(hào)不是有效的匹配，有效的匹配只到前一個(gè)位置，計(jì)算從開始位置到有效位置有多少位，i - 1 - start + 1（1到7有幾個(gè)數(shù)？7-1+1 =7對不對），就是i-start。這個(gè)完事之后咱從下一位開始匹配，更新一下start。
• 第二種是棧沒空，到此位置還是有效的，然后我們需要pop掉一個(gè)元素。pop完了又出問題了，棧空了，棧沒空。（楊宗緯《我變了，我沒變》）
  假設(shè)棧空了，你能咋辦，匹配完了唄，算一下幾個(gè)括號(hào)，i - start + 1，這個(gè)不想解釋了，參考上面的說法吧。
  假設(shè)棧沒空，哎沒匹配完，有效的有幾個(gè)啊，注意哦當(dāng)前i位置是有效的，然后前面pop掉一個(gè)i - (stack[-1] + 1) +1 ，嗯算完了i - stack[-1]。stack是啥，你們覺得是啥，當(dāng)然是左括號(hào)對應(yīng)的下標(biāo)啊。

2.2 正確做法

做出這道題總共分三步：
第一步，整個(gè)循環(huán)，遍歷輸入字符串。
第二步，設(shè)置一個(gè)start，隨時(shí)更新著，設(shè)置一個(gè)stack，記錄下左括號(hào)的下標(biāo)。
第三步，開始操作，按照上一節(jié)的疑點(diǎn)3操作，對著代碼看，可能更清楚一點(diǎn)。

3.python代碼

class Solution:
    def longestValidParentheses(self, s):
        nlen = len(s)
        i = 0
        new_stack = []
        lk = 0
        start = 0
        if nlen <= 1:
            return 0
        while i < nlen:
            # print(i)
            # print(new_stack)
            # print('start', start)
            if s[i] == '(':
                new_stack.append(i)
            else:
                if new_stack:
                    new_stack.pop()
                    if new_stack == []:
                        lk = max(lk, i - start + 1)
                    else:
                        # print(2)
                        lk = max(lk, i - new_stack[-1])
                else:
                    lk = max(lk, i - start)
                    start = i + 1
            i += 1
        return lk