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.
寻找最大有效匹配括号的长度。
不解释题目意思了，大家都懂吧……
代码如下：
class Solution {
public:
int longestValidParentheses(string str) {
int maxLen = ;
int count = ;
stack<int> s;
int firstLeft = ;
for(int i = ; i < str.size(); i++){
//i代表当前的下标
if(str[i] == '('){
s.push(i); // 遇到（ 就push
}
else{
//str[i] == ')'
if(!s.empty()){
//栈非空
s.pop();
if(!s.empty()){
//pop后栈里还有元素，比如"()(()()"来举例
int lastIndex = s.top(); //lastIndex 是中间那个（ 的下标，即为2
int len = i - lastIndex; // 此时 i = 4或者 6，以6举例的话， len等于4
if(len > maxLen) // if ( 4 > 2) true maxLen = 4
maxLen = len;
}
else{
//pop后没有元素了，比如"(())"情况举例
int len = i - firstLeft + ; //此时firstLeft等于0，i 等于3的话，len等于 3 - 0 + 1 = 4
if(len > maxLen){
maxLen = len;
}
}
}
else{
firstLeft = i + ; //栈为空的时候遇到），将firstLeft移到i 的下一个。
}
}
}
return maxLen;
}
};
解题思路：
因为存在类似于"（）（（）（）"的情况，如果我们仅仅只是遇到（就压栈，遇到）就弹栈的话，然后通过一个count和一个maxLen来计算当前的最大长度，就会遇到问题。
因为第二个"（"是到最后也没有匹配到的，他应该是将左边和右边的子串分割开来了，即左边的长度为2，右边的长度为4。可如果按照我之前的那个只有当栈为空且遇到的是"）"的时候字符串才出现分割的想法的话，“（）（（）（）”的长度就是6了，因为他一直都没有被分割。
那么，我们如何来标记那些已经压进栈里的却没有得到"）"匹配，起着分割左右子串作用的"（"符号呢？
这样，我们的stack的元素类型不是char 了，不存"（"，"）"这样的字符，而是存下每一个"（"字符的下标，是int类型。
当遇到一个"）"而且栈不为空的时候，弹栈。当弹栈之后发现栈还是不为空的时候，此时栈顶的那个元素lastIndex即为没有匹配的那个"（" 的下标值了，我们用此时的下标 i 和lastIndex的差值就知道了真正的有效括号的长度，再将他和maxLen比较，让maxLen等于他们中的较大值。