Longest Valid Parentheses
?
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.
?
思路：此题也是参看网上资料解出。我自己做出来的是循环O(n^3)的时间复杂度，提交果断超时。我解法的思想是先判断字符串为奇数还是偶数，偶数就本字符串开始，判断是否为有效括号对，是返回，不是，长度减2，循环截取s，直到找到最大为止。
另一种方法参看了别人的思路，自己写的代码，总体思想是循环遍历S,用两个栈保存，一个保存“（）”,一个保存索引，两个栈的操作相同。最后未出栈的元素就是无法匹配的元素，同时也是各个有效括号组的分界点，据此由各个索引相减求最大值即可。
同一个复杂字符串，方法一耗时1790ms，方法二耗时1ms.效率差距巨大。
方法一代码：
?
public int longestValidParentheses(String s) {
int len = s.length();
if(len <= 1){
return 0;
}
int startLen;
int validLen = 0;
//长度为偶数
if((len & 1) == 0){
startLen = len;
}else{
startLen = len -1;
}
boolean isBreak = false;
while(startLen > 0){
if(isBreak) break;
for(int i = 0; i + startLen <= len; i++){
String temp = s.substring(i,i+startLen);
int k = lenValid(temp);
if(k > validLen){
validLen = k;
isBreak = true;
break;
}
}
startLen -= 2;
}
return validLen;
}
//str是否有效括号，有效返回len,无效返回-1
private int lenValid(String str){
Stack
st = new Stack
(); for(int i = 0; i< str.length();i++){ if(st.isEmpty() || st.peek() != '(' || str.charAt(i) != ')'){ st.push(str.charAt(i)); }else{ st.pop(); } } if(st.isEmpty()){ return str.length(); } return -1; }
方法二代码：
?
?
public int longestValidParentheses1(String s) {
Stack
st = new Stack
();//保存() Stack
si = new Stack
();//保存()的索引 si.push(-1);//将-1作为一个分界起始值 for(int i = 0; i < s.length(); i++){ if(st.isEmpty() || st.peek() != '(' || s.charAt(i) != ')'){ st.push(s.charAt(i));//入栈 si.push(i); }else{ st.pop();//出栈 si.pop(); } } //si.push(s.length()-1); //每一个未出栈的元素都是各个有效组的分界点 int end = s.length();//起始点 int max = 0;//最大长度 while(!si.isEmpty()){ int start = si.pop(); max = end - start - 1 > max ? end - start -1:max; end = start; } return max; }
?
?