一、題目
給定一個只包含 '(' 和 ')' 的字符串，找出最長的包含有效括號的子串的長度。
示例 1:
輸入: "(()"
輸出: 2
解釋: 最長有效括號子串為 "()"
示例 2:
輸入: ")()())"
輸出: 4
解釋: 最長有效括號子串為 "()()"
二、解答
2.1方法一：動態(tài)規(guī)劃
2.1.1 思路
2.1.1.1 定義動態(tài)規(guī)劃數(shù)組
dp [ i ] 代表以下標 i 結(jié)尾的合法序列的最長長度，例如下圖
下標 1 結(jié)尾的最長合法字符串長度是 2，下標 3 結(jié)尾的最長字符串是 str [ 0 , 3 ]，長度是 4 。
2.1.1.2 規(guī)律
- 首先我們初始化所有的 dp 都等于零。
- 以左括號結(jié)尾的字符串一定是非法序列，所以 dp 是零，不用更改。
- 以右括號結(jié)尾的字符串分兩種情況。
a.右括號前邊是 ( ，類似于 ……（）。
dp [ i ] = dp [ i - 2] + 2 （前一個合法序列的長度，加上當前新增的長度 2）
類似于上圖中 index = 3 的時候的情況。
dp [ 3 ] = dp [ 3 - 2 ] + 2 = dp [ 1 ] + 2 = 2 + 2 = 4
b.右括號前邊是 )，類似于 ……））。
此時我們需要判斷 i - dp[i - 1] - 1 （前一個合法序列的前邊一個位置） 是不是左括號。
例如上圖的 index = 7 的時候，此時 index - 1 也是右括號，我們需要知道 i - dp[i - 1] - 1 = 7 - dp [ 6 ] - 1 = 4 位置的括號的情況。
而剛好 index = 4 的位置是左括號，此時 dp [ i ] = dp [ i - 1 ] + dp [ i - dp [ i - 1] - 2 ] + 2 （當前位置的前一個合法序列的長度，加上匹配的左括號前邊的合法序列的長度，加上新增的長度 2），也就是 dp [ 7 ] = dp [ 7 - 1 ] + dp [ 7 - dp [ 7 - 1] - 2 ] + 2 = dp [ 6 ] + dp [7 - 2 - 2] + 2 = 2 + 4 + 2 = 8。
如果 index = 4 不是左括號，那么此時位置 7 的右括號沒有匹配的左括號，所以 dp [ 7 ] = 0 ，不需要更新。
2.1.1 實現(xiàn)
public int longestValidParentheses(String s) {
int maxans = 0;
int dp[] = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
//右括號前邊是左括號
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
//右括號前邊是右括號，并且除去前邊的合法序列的前邊是左括號
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
時間復雜度：遍歷了一次，O（n）。
空間復雜度：O（n）。
2.2方法二：棧
2.2.1 思路
從左到右掃描字符串，棧頂保存當前掃描的時候，合法序列前的一個位置位置下標是多少，啥意思嘞？
我們掃描到左括號，就將當前位置入棧。
掃描到右括號，就將棧頂出棧（代表棧頂?shù)淖罄ㄌ柶ヅ涞搅擞依ㄌ枺缓蠓謨煞N情況。
棧不空，那么就用當前的位置減去棧頂?shù)拇娴奈恢?，然后就得到當前合法序列的長度，然后更新一下最長長度。
棧是空的，說明之前沒有與之匹配的左括號，那么就將當前的位置入棧。
看下圖示，更好的理解一下。
2.2.2 實現(xiàn)
public int longestValidParentheses(String s) {
int maxans = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
時間復雜度： O（n）。
空間復雜度：O（n）。
2.3方法三：大神操作
2.3.1 思路
保持時間復雜度是 O（n），將空間復雜度優(yōu)化到了 O（1），它的動機是怎么想到的沒有理出來，就介紹下它的想法吧。
從左到右掃描，用兩個變量 left 和 right 保存的當前的左括號和右括號的個數(shù)，都初始化為 0 。
如果左括號個數(shù)等于右括號個數(shù)了，那么就更新合法序列的最長長度。
如果左括號個數(shù)大于右括號個數(shù)了，那么就接著向右邊掃描。
如果左括號數(shù)目小于右括號個數(shù)了，那么后邊無論是什么，此時都不可能是合法序列了，此時 left 和 right 歸 0，然后接著掃描。
從左到右掃描完畢后，同樣的方法從右到左再來一次，因為類似這樣的情況 ( ( ( ) ) ，如果從左到右掃描到最后，left = 3，right = 2，期間不會出現(xiàn) left == right。但是如果從右向左掃描，掃描到倒數(shù)第二個位置的時候，就會出現(xiàn) left = 2，right = 2 ，就會得到一種合法序列。
2.3.2 實現(xiàn)
public static int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right >= left) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left >= right) {
left = right = 0;
}
}
return maxlength;
}
