Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is"()()"
此题要求一个括号字符串中最长的合法的括号串的长度。 遇到括号问题，想当然的用栈来解决，可以尝试每一个以'(‘开头的字符串，用栈求出其最长合法括号串的长度，然后求全局最大值，如下：
class Solution {
public:
int longestValidParentheses(string s)
{
int n = s.size(), maxval = 0;
for (int i = 0; i < n; i++) { if (s[i] == ‘(‘) {
stack<char> sc;
sc.push(s[i]);
int cur = 0;
for (int j = i + 1; j < n; j++) {
char t = sc.top();
if (s[j] == ‘)’)
{ if (t == ‘(‘) {
sc.pop();
cur++; } else break;
}
sc.push(s[j]);
}
if (cur > maxval)
maxval = cur; }
}
return maxval * 2;
}
};但是这个算法是$O(n^2)$的，TLE。
后来看题解，居然有$O(n)$的解法，厉害，如下：
class Solution {
public:
int longestValidParentheses(string s)
{
int n = s.size(), maxval = 0, start = -1; // start初始化为-1
stack<int> si;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
si.push(i); //左括号无条件压栈
} else { //右括号不压栈
if (si.empty()) {
start = i; //以右括号作为新的起点
} else {
si.pop();
if (si.empty()) // ()()() or (()())
maxval = max(maxval, i - start);
else // (() 用当前栈顶索引作为起点
maxval = max(maxval, i - si.top());
}
}
}
return maxval;
}
};本算法提交AC，用时12MS。
它也是用堆栈，但是堆栈里存的不是括号，而是括号的索引。左括号无条件压栈，右括号不压栈，只是作为计算括号对的长度的起点（其实起点应该是右括号索引+1，但是计算长度的时候用右括号索引更方便）。
所以栈里面只有左括号，当右括号来了，且栈为空时，说明之前已经配对完了，要开始新的配对，所以设置新的起点。
如果栈不为空，则pop。如果pop完之后栈为空，也说明配对完成，可以更新最佳长度；如果pop完之后栈里还有左括号，则是(((()这种类型，左括号更多，则匹配的起点应该是栈顶的索引，而不是之前设置的右括号索引+1，如下：
(((() ^ ^二刷。比较容易理解的是动态规划的方法。设dp[i]表示以字符i结尾的最长合法括号串的长度，则所有左括号对应的dp[i]都等于0，因为合法的括号串都是以右括号结尾的。
如果s[i]==’)’，有两种情况。第一种情况是s[i-1]='(‘，则s[i]和s[i-1]配对，所以dp[i]=dp[i-2]+2。第二种情况是s[i-1]也=’)’，则s[i]无法和s[i-1]配对，但是如果向前跨过s[i-1]对应的合法字符串后有左括号出现，则s[i]有望作为一个外围的右大括号配对成功，如下图所示，最右边的是第s[i]=’)’，向前跨过了(xxx)，和前一个左括号配对成功。这种情况下，dp[i]=dp[i-1]+2，又因为配对的左括号前面还有可能是合法的括号串，所以还要加上dp[i-dp[i-1]-1-1]。
xxx((xxxx))
完整代码如下：
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
vector<int> dp(n, 0);
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == ')') {
if (i > 0 && s[i - 1] == '(') {
dp[i] += 2;
if (i >= 2)dp[i] += dp[i - 2];
}
else if (i > 0 && s[i - 1] == ')') {
int left = i - dp[i - 1] - 1;
if (left >= 0 && s[left] == '(') {
dp[i] = dp[i - 1] + 2;
if (left > 0)dp[i] += dp[left - 1];
}
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};本代码提交AC，用时4MS。
至于用栈的方法，是这样的：栈中只插入左括号的下标，以便来了右括号后，把配对的左括号弹出，剩下栈顶左括号下标作为之前弹出的合法括号串的起始位置。如果栈顶为空，且来了右括号，则这个右括号肯定配对失败，所以也把它的下标入栈，用来充当后续合法括号串的起始位置。
更简洁易懂的代码如下：
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int ans = 0;
stack<int> stk;
stk.push(-1);
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
stk.push(i);
}
else {
if (!stk.empty())stk.pop();
if (stk.empty()) {
stk.push(i);
}
else {
ans = max(ans, i - stk.top());
}
}
}
return ans;
}
};本代码提交AC，用时4MS。