題目

給你一個只包含 ‘(’ 和 ‘)’ 的字符串，找出最長有效（格式正確且連續）括號 子串 的長度。

左右括號匹配，即每個左括號都有對應的右括號將其閉合的字符串是格式正確的，比如 “(()())”。

思路

方法一：棧
括號類的題目我們首先想到的是應該是用棧來做，這道題也不例外。對于這種有關最值的問題我們先不要管最值，先思考我們如何得到有效括號子串的長度。其實我們仔細想一想子串的長度不就是最后一個有效的右括號的下標減去最后一個無效的右括號下標嗎，例如這個字符串")(())()“我們來觀察一下有效子串的長度應該如何更新，不就是后面的右括號下標減去第一個右括號的下標嗎。所以我們只要保證棧底里永遠存著一個最后一個無效的右括號下標即可在我們每次匹配完成后就可以用當前下標去減去這個下標就可以得到有效括號子串的長度了。
所有我們還是正常對左右括號進行處理，遇到左括號進行push，遇到右括號進行pop同時更新最長子串的值。為了保證我們pop時棧不為空也就是如果字符串開頭不是左括號而是右括號例如”())“這樣，我們先對棧push一個-1。
方法二：動態規劃
對于這道題我們是否還有其他的思路，當我們遇到一個有效子串也就是一個左括號一個右括號，那么新的有效長度不就是在原來的基礎上進行+2嗎。所以我們是否可以設置一個數組來存儲以當前位置為結尾的有效子串長度。
那么對于左括號和右括號來說數組的值分別是多少呢，對于左括號來說如果以一個左括號為結尾那么有效子串長度毫無疑問就是0，而對于一個右括號來說子串的長度就需要進行討論了。所以我們在創建數組時可以先將其全部置為0然后只對遇到右括號時再進行剩下的處理。那么遇到右括號一共不就兩種情況嗎前一個位置是左括號和前一個位置不是左括號，如果前一個位置是左括號那么不就匹配成功了我們就可以在原本的基礎上對子串長度加2即可。關鍵是如果前一個位置不是左括號呢，這時候我們就需要再做一個判斷也就是在去除那些有效子串后的位置是不是左括號例如這種情況”()(()())",當我們遇到最后一個右括號時我們發現它也是匹配成功的只是匹配的遠了點所以我們需要判斷在去除了前面的有效子串后的前一個位置是不是左括號，如果是我們就可以在數組的再前一個位置的基礎上進行+2。
一樣的我們發現數組的每一個位置都是答案所以這也是動態規劃思想。

代碼

方法一：棧

class Solution {
public:int longestValidParentheses(string s) {stack<int> st;st.push(-1);int res = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {// 如果遇到左括號就插入棧中st.push(i);} else {// 如果是右括號// 先對棧進行pop，因為我們提前插入了一個-1所以棧不可能為空st.pop();// 如果在pop后棧為空了說明從這個位置開始要重新計算長度了if (st.empty()) {st.push(i);} else {res = max(res, i - st.top());}}}return res;}
};

方法二：動態規劃

class Solution {
public:int longestValidParentheses(string s) {int res = 0;int n = s.size();// 使用數組存儲以當前位置為結尾的符合條件的最長子串的長度vector<int> dp(n, 0);for (int i = 1; i < n; i++) {// 如果為左括號則不用管因為以左括號為結尾肯定不符合條件if (s[i] == ')') {// 有兩種情況，i-1是左括號或者右括號if (s[i - 1] == '(') {// 如果是左括號則說明括號匹配上了dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;}// 如果為右括號// 還需要判斷去除前面的有效括號后的那位字符是不是左括號// 如果是就匹配上了else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {dp[i] = dp[i - 1] +(i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;}res = max(res, dp[i]);}}return res;}
};