1.題目
原題：
給定一個(gè)只包含 '(' 和 ')' 的字符串甥雕，找出最長(zhǎng)的包含有效括號(hào)的子串的長(zhǎng)度贬堵。
例子：
輸入: "(()"
輸出: 2
解釋: 最長(zhǎng)有效括號(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（下面簡(jiǎn)稱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對(duì)不對(duì)）冻璃，就是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)對(duì)應(yīng)的下標(biāo)啊台夺。
2.2 正確做法
做出這道題總共分三步：
第一步，整個(gè)循環(huán)痴脾，遍歷輸入字符串颤介。
第二步，設(shè)置一個(gè)start，隨時(shí)更新著滚朵，設(shè)置一個(gè)stack冤灾，記錄下左括號(hào)的下標(biāo)。
第三步辕近，開始操作韵吨，按照上一節(jié)的疑點(diǎn)3操作，對(duì)著代碼看移宅，可能更清楚一點(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
