今天是紀錄LeetCode解題的第三十二天
是一題困難題

第三十二題題目：Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

給定一個僅包含'('和')'的字串，傳回最長有效(格式正確)括號的長度子字串

解題思路

初始化stack存索引(一開始先存-1)，表示「合法子字串起點前一個位置」，當遇到左括號，把當前左括號的索引存入stack，遇到右括號時，pop出stack的元素，如果stack空了，表示無法配對，就把目前索引存入stack，否則用當前的索引減掉stack目前最上方的索引(i - stack[-1])更新最長長度

程式碼

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_len = 0
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        return max_len

為什麼初始化要先放-1在Stack裡?

放-1是為了處理一開始就出現合法括號的情況
假設s = "()"，一開始遇到左括號，儲存索引0，stack = [-1,0]，接著遇到右括號，pop出0，並且算當前索引1減掉stack[-1]的值-1，也就是1 - (-1) = 2，所以合法括號子字串長度是2

執行過程

初始狀態

• s = ( ) ) ( ( ) )
• stack = [-1]
• max_len = 0