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.
题意：求最长的合法括号长度
思路1，用栈：1.遍历字符串，当遇到'('的时候，把其索引放入堆栈，当遇到')'时候，如果栈顶是'('，则出栈操作一次，否则索引入栈
2.当栈为空时候，说明字符串全体合法，返回字符串长度
3.如果栈不为空，则比较栈中相邻索引的“空洞”长度，最长的空洞即为所求
class Solution {
public:
int longestValidParentheses(string s) {
int n=s.length(),i,longest=;
stack<int> st;
for(i=;i<n;i++){
if('('==s[i])
st.push(i);
else{
if(!st.empty()){
if(s[st.top()]=='(')
st.pop();
else
st.push(i);
}
else{
st.push(i);
}
}
}
if(st.empty()) longest = n;
else{
int rear=n,front=;
while(!st.empty()){
front=st.top();
st.pop();
longest = max(longest,rear--front);
rear = front;
}
longest = max(longest,front);
}
return longest;
}
};
思路2：动态规划
用longest[]记录字符串中截至每个位置时的最长合法字符串长度
如果s[i]为'('，那么longest[i]为0，因为左右以'('结尾的字符串肯定不合法，为0
如果s[i]为')'，那么分两种情况
1.当s[i-1]为'('时候， longest[i] = longest[i-2] + 2
2.当s[i-1]为')'，和s[i-longest[i-1]-1] == '('时，longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]；
longest[i-longest[i-1]-2]代表上一个以')'结尾的合法字符串
class Solution {
public:
int longestValidParentheses(string s) {
int len=s.length();
if(len<=)
return ;
int curmax=;
vector<int> longest(len,);
for(int i=;i<len;i++){
if(')'==s[i]){
if('('==s[i-]){
longest[i]=(i->?longest[i-]+:);
curmax=max(longest[i],curmax);
}
else{
if(i-longest[i-]->=&&s[i-longest[i-]-]=='('){
longest[i]=longest[i-]++(i-longest[i-]->?longest[i-longest[i-]-]:);
curmax=max(longest[i],curmax);
}
}
}
}
return curmax;
}
};