一丙号、題目
給定一個(gè)只包含 '(' 和 ')' 的字符串，找出最長的包含有效括號(hào)的子串的長度牲证。
示例 1:
輸入: "(()"
輸出: 2
解釋: 最長有效括號(hào)子串為 "()"
示例 2:
輸入: ")()())"
輸出: 4
解釋: 最長有效括號(hào)子串為 "()()"
二巨双、解答
2.1方法一：動(dòng)態(tài)規(guī)劃
2.1.1 思路
2.1.1.1 定義動(dòng)態(tài)規(guī)劃數(shù)組
dp [ i ] 代表以下標(biāo) i 結(jié)尾的合法序列的最長長度，例如下圖
下標(biāo) 1 結(jié)尾的最長合法字符串長度是 2熔恢，下標(biāo) 3 結(jié)尾的最長字符串是 str [ 0 , 3 ]脐湾，長度是 4 臭笆。
2.1.1.2 規(guī)律
- 首先我們初始化所有的 dp 都等于零。
- 以左括號(hào)結(jié)尾的字符串一定是非法序列秤掌，所以 dp 是零愁铺，不用更改。
- 以右括號(hào)結(jié)尾的字符串分兩種情況闻鉴。
a.右括號(hào)前邊是 ( 茵乱，類似于 ……（）。
dp [ i ] = dp [ i - 2] + 2 （前一個(gè)合法序列的長度孟岛，加上當(dāng)前新增的長度 2）
類似于上圖中 index = 3 的時(shí)候的情況瓶竭。
dp [ 3 ] = dp [ 3 - 2 ] + 2 = dp [ 1 ] + 2 = 2 + 2 = 4
b.右括號(hào)前邊是 )，類似于 ……））渠羞。
此時(shí)我們需要判斷 i - dp[i - 1] - 1 （前一個(gè)合法序列的前邊一個(gè)位置） 是不是左括號(hào)斤贰。
例如上圖的 index = 7 的時(shí)候，此時(shí) index - 1 也是右括號(hào)次询，我們需要知道 i - dp[i - 1] - 1 = 7 - dp [ 6 ] - 1 = 4 位置的括號(hào)的情況荧恍。
而剛好 index = 4 的位置是左括號(hào)，此時(shí) dp [ i ] = dp [ i - 1 ] + dp [ i - dp [ i - 1] - 2 ] + 2 （當(dāng)前位置的前一個(gè)合法序列的長度屯吊，加上匹配的左括號(hào)前邊的合法序列的長度送巡，加上新增的長度 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 不是左括號(hào)骗爆，那么此時(shí)位置 7 的右括號(hào)沒有匹配的左括號(hào)，所以 dp [ 7 ] = 0 蔽介，不需要更新摘投。
2.1.1 實(shí)現(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) == ')') {
//右括號(hào)前邊是左括號(hào)
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
//右括號(hào)前邊是右括號(hào)糟需，并且除去前邊的合法序列的前邊是左括號(hào)
} 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;
}
時(shí)間復(fù)雜度：遍歷了一次，O（n）谷朝。
空間復(fù)雜度：O（n）洲押。
2.2方法二：棧
2.2.1 思路
從左到右掃描字符串，棧頂保存當(dāng)前掃描的時(shí)候圆凰，合法序列前的一個(gè)位置位置下標(biāo)是多少杈帐，啥意思嘞？
我們掃描到左括號(hào)专钉，就將當(dāng)前位置入棧挑童。
掃描到右括號(hào)，就將棧頂出棧（代表?xiàng)ｍ數(shù)淖罄ㄌ?hào)匹配到了右括號(hào)）跃须，然后分兩種情況站叼。
棧不空，那么就用當(dāng)前的位置減去棧頂?shù)拇娴奈恢霉矫瘢缓缶偷玫疆?dāng)前合法序列的長度尽楔，然后更新一下最長長度。
棧是空的第练，說明之前沒有與之匹配的左括號(hào)阔馋，那么就將當(dāng)前的位置入棧。
看下圖示娇掏，更好的理解一下呕寝。
2.2.2 實(shí)現(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;
}
時(shí)間復(fù)雜度： O（n）。
空間復(fù)雜度：O（n）婴梧。
2.3方法三：大神操作
2.3.1 思路
保持時(shí)間復(fù)雜度是 O（n）下梢，將空間復(fù)雜度優(yōu)化到了 O（1），它的動(dòng)機(jī)是怎么想到的沒有理出來塞蹭，就介紹下它的想法吧孽江。
從左到右掃描，用兩個(gè)變量 left 和 right 保存的當(dāng)前的左括號(hào)和右括號(hào)的個(gè)數(shù)浮还，都初始化為 0 竟坛。
如果左括號(hào)個(gè)數(shù)等于右括號(hào)個(gè)數(shù)了，那么就更新合法序列的最長長度钧舌。
如果左括號(hào)個(gè)數(shù)大于右括號(hào)個(gè)數(shù)了担汤，那么就接著向右邊掃描。
如果左括號(hào)數(shù)目小于右括號(hào)個(gè)數(shù)了洼冻，那么后邊無論是什么崭歧，此時(shí)都不可能是合法序列了，此時(shí) left 和 right 歸 0撞牢，然后接著掃描率碾。
從左到右掃描完畢后叔营，同樣的方法從右到左再來一次，因?yàn)轭愃七@樣的情況 ( ( ( ) ) 所宰，如果從左到右掃描到最后绒尊，left = 3，right = 2仔粥，期間不會(huì)出現(xiàn) left == right婴谱。但是如果從右向左掃描，掃描到倒數(shù)第二個(gè)位置的時(shí)候躯泰，就會(huì)出現(xiàn) left = 2谭羔，right = 2 ，就會(huì)得到一種合法序列麦向。
2.3.2 實(shí)現(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;
}
