問題

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

例子

For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

分析

方法一：棧

遍歷字符串，如果當(dāng)前字符為 ( , 入棧；如果是 ) ，檢測棧的情況：如果棧為空，入棧；否則檢查棧頂，如果為 ( ，出棧；否則入棧。注意，也要把當(dāng)前字符的下標入棧。
將棧的元素一一出棧，即可得到每一段合法的括號表達式的長度。假設(shè)字符串為")()(()))()("，遍歷完之后，棧應(yīng)該變成 ) 0, ) 7, ( 10?？梢郧宄乜吹剑址袃啥魏戏ǖ睦ㄌ柋磉_式，長度分別為7 - 0 - 1 = 6、10 - 7 - 1 = 2。最長長度為6。

方法二：動態(tài)規(guī)劃

假設(shè)待驗證字符串為S

1. 狀態(tài)表
   dp[i] 表示以S[i - 1]作為結(jié)尾的最長合法字符串的長度
2. 初始狀態(tài)
   dp[0] = dp[1] = 0 長度為0或者1的字符串顯然不合法
3. 狀態(tài)轉(zhuǎn)移方程
   dp[i] = dp[i - 2] + 2 if s[i - 1] == ')' && s[i - 2] = '('
   注：表示這種情況：...() **
   顯然dp[i]的大小等于...的最大合法字符串的長度（dp[i - 2]）+2
   dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]; if s[i - 1] == ')' && s[i - 2] = ')' && s[i - 2 - dp[i - 1]] == '('
   注：表示這種情況：...(()) **
   第一個 ( 是s[i - 2 - dp[i - 1]] ，第一個 ) 是s[i - 2]，第二個 ) 是s[i - 1]?？傞L度=...的最大合法字符串的長度（dp[i - 2 - dp[i - 1]]）+ 2（s[i - 2 - dp[i - 1]]和s[i - 1]匹配的一對括號）+ dp[i - 1]（中間的兩個括號）

要點

• 熟練運用棧和動態(tài)規(guī)劃；
• 動態(tài)規(guī)劃分為兩種，一種狀態(tài)本身就是所求的變量，另一種則不是，但是所求的變量可以在更新狀態(tài)表的過程中得到。

時間復(fù)雜度

O(n)

空間復(fù)雜度

O(n)

代碼

方法一

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<pair<char, int>> es;
        for (int i = 0; i < s.size(); i++) {
            if (es.empty() || s[i] == '(') es.push(make_pair(s[i], i));
            else {
                if (es.top().first == '(') es.pop();
                else es.push(make_pair(s[i], i));
            }
        }

        int longestLen = 0, last = s.size();
        while (!es.empty()) {
            longestLen = max(longestLen, last - es.top().second - 1);
            last = es.top().second;
            es.pop();
        }
        longestLen = max(longestLen, last);
        return longestLen;
    }
};

方法二

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        int longestLen = 0;
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] == ')') {
                if (s[i - 2] == '(') 
                    dp[i] = dp[i - 2] + 2;
                else if (s[i - 2 - dp[i - 1]] == '(')
                    dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]];
                longestLen = max(longestLen, dp[i]);
            }
        }
        return longestLen;
    }
};