题目链接：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.
这道题的要求是在仅包含“(”和“)”的字符串中，找到最长的括号匹配的子串，返回其长度。
对于括号匹配，和Valid Parentheses同样的思路，用栈维护左括号，即在读取字符串的时候，遇到左括号就入栈。遇到右括号就出栈，同时判断当前括号匹配的子串是否为最长子串。
不过在判断括号匹配的子串的长度的时候，有一些值得注意的问题，其中需要借助变量l记录当前括号匹配的子串的左侧位置：
- 如果当前栈为空，这说明当前的右括号并不构成括号匹配的子串，则l移到下一位置。
- 如果当前栈不为空，弹出栈顶元素。此时，如果栈为空，说明加上当前的右括号可以构成括号匹配的子串，其子串长度就为l位置到当前位置的长度；如果栈不为空，则栈顶元素后面的括号对肯定是匹配的，因此子串长度就为栈顶元素位置的后一位置到当前位置的长度。
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
public:
int longestValidParentheses(string s)
{
int res = 0, l = 0;
stack<int> si;
for(int i = 0; i < s.size(); ++ i)
{
if(s[i] == '(')
si.push(i);
else
{
if(si.empty())
l = i + 1;
else
{
si.pop();
if(si.empty())
res = max(res, i - l + 1);
else
res = max(res, i - si.top());
}
}
}
return res;
}
};
当然，这道题还可以用动态规划的方法处理，具体请参考这里。