leetcode32 题解
题目
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Example 3:
Input: s = ""
Output: 0
Constraints:
0 <= s.length <= 3 * 104s[i]is'(', or')'.
题解
参考LeetCode 32:最长有效括号题解(贪心算法/DP/栈) – zempty 笔记 – 思考与行动，让未来更清晰
class Solution {
public:
int longestValidParentheses(const string& s) {
stack<int> pars;
pars.push(-1);
int res =0;
char tmp=0;
int ssize = s.size();
for( int i=0;i<ssize ;i++){
if(s[i]==')'){
pars.pop();
if(pars.empty()){
pars.push(i);//如果弹出之后发现栈空了，其实代表了 没有匹配到。也就是说，我们把上一次对于开始边界打的标记弹出来了，而不是弹出了一个期望的左括号。这样我们就要重新对开始的边界做一个标记。同时，栈当中的每一个元素的底下的元素就是对于这个开始边界的标记。
}
else {
res= max(res,i-pars.top());// 这里相当于找到了开始的边界
}
}
if(s[i] == '('){
pars.push(i);//这里代表 一个准备匹配的括号
}
}
return res;
}
};
class Solution {
public:
int longestValidParentheses(const string& s) {
int slength = s.length();
vector<int> validate(slength,0);
int res =0;
for(int i=0;i<slength;i++){
if(s [i] ==')'){//validate标注的是每一个 右括号 的位置，标注的是严格符合要求的子串的长度
if(i==1 && s[0] == '('){
validate[i]=2;
} else if(i>1 && s[i-1]=='('){
validate[i]=validate[i-2]+2;
} else if(
i>1
&& s[i-1]==')'
&& validate[i-1]!=0
&& i - 1 - validate [ i - 1 ]>=0
&& s[i-1-validate[i-1]] =='('
){
validate[i]=validate[i-1]+2+(i-2-validate[i-1]>=0?validate[i-2-validate[i-1]]:0);//"()(())" 让这里能够去连接前面的内容，同时防止溢出。
}
}
res = max(validate[i],res);
}
//copy(validate.begin(),validate.end(),ostream_iterator<int>(cout," "));
//cout<<endl;
return res;
}
};