【LeetCode练习题】Longest Valid Parentheses

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.

寻找最大有效匹配括号的长度。

不解释题目意思了，大家都懂吧……

代码如下：

 1 class Solution {
 2 public:
 3     int longestValidParentheses(string str) {
 4         int maxLen = 0;
 5         int count = 0;
 6         stack<int> s;
 7         int firstLeft = 0;
 8         
 9         for(int i = 0; i < str.size(); i++){
10             //i代表当前的下标
11             if(str[i] == '('){
12                 s.push(i); // 遇到（ 就push
13             }
14             else{
15                 //str[i] == ')'
16                 if(!s.empty()){
17                     //栈非空
18                     s.pop();
19                     if(!s.empty()){
20                         //pop后栈里还有元素，比如"()(()()"来举例
21                         int lastIndex = s.top(); //lastIndex 是中间那个（ 的下标，即为2
22                         int len = i - lastIndex; // 此时 i = 4或者 6，以6举例的话， len等于4
23                         if(len > maxLen)         // if ( 4 > 2)  true     maxLen = 4
24                             maxLen = len;
25                     }
26                     else{
27                         //pop后没有元素了，比如"(())"情况举例
28                         int len = i - firstLeft + 1; //此时firstLeft等于0，i 等于3的话，len等于 3 - 0 + 1 = 4
29                         if(len > maxLen){
30                             maxLen = len;
31                         }
32                     }
33                 }
34                 else{
35                     firstLeft = i + 1; //栈为空的时候遇到），将firstLeft移到i 的下一个。
36                 }
37             }
38         }
39         return maxLen;
40     }
41 };

解题思路：

因为存在类似于"（）（（）（）"的情况，如果我们仅仅只是遇到（就压栈，遇到）就弹栈的话，然后通过一个count和一个maxLen来计算当前的最大长度，就会遇到问题。

因为第二个"（"是到最后也没有匹配到的，他应该是将左边和右边的子串分割开来了，即左边的长度为2，右边的长度为4。可如果按照我之前的那个只有当栈为空且遇到的是"）"的时候字符串才出现分割的想法的话，“（）（（）（）”的长度就是6了，因为他一直都没有被分割。

那么，我们如何来标记那些已经压进栈里的却没有得到"）"匹配，起着分割左右子串作用的"（"符号呢？

这样，我们的stack的元素类型不是char 了，不存"（"，"）"这样的字符，而是存下每一个"（"字符的下标，是int类型。

当遇到一个"）"而且栈不为空的时候，弹栈。当弹栈之后发现栈还是不为空的时候，此时栈顶的那个元素lastIndex即为没有匹配的那个"（" 的下标值了，我们用此时的下标 i 和lastIndex的差值就知道了真正的有效括号的长度，再将他和maxLen比较，让maxLen等于他们中的较大值。