32. Longest Valid Parentheses
题目描述
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 "()()"
解题思路
括号匹配是一道非常经典的问题。考虑一个字符串，如果这是一个括号能成功匹配的字符串，它应该具有这样的性质：前括号和反括号的数量相等；在这个前提下，对于s的子串
，若
是反括号，那么，
中的前括号一定比反括号要多。
根据这两个性质，要判断一个字符串可以考虑这样的策略：用栈来处理这个字符串。遇到前括号时，将前括号入栈；遇到反括号时，若栈顶为空，则说明子串前括号与反括号一样多，不符合条件，该串不合法；若栈顶不为空，则将栈顶出栈。最后若栈为空，则合法。
在这道题里，我们也可以用这个策略来判断串s是否为合法的括号匹配字符串，若s是合法的括号匹配字符串，则最长子括号匹配字符串的长度就是s的长度。但如果不是呢？我们要如何找出s中最长的括号匹配字符串呢？
假设s是这样的字符串：，t为合法的括号匹配字符串，而p则是夹在它们中的非法字符（注意，这里t可以是空串，因为空串也是合法的括号匹配字符串）。我们继续用上面提到的方法来遍历这个字符串，不同的是，在遇到不合法的情况的时候不退出。在遍历完一遍之后，栈中留存的是串
，因为夹在它们中间的串都会能正确匹配，最后留下空的栈空间。在找到这些夹在中间的元素之后，我们就可以通过计算p的下标的差值的方式，找到最长的子串。最后返回最大的差值即可。
要注意一下长度的计算公式：
时间复杂度分析
遍历一次字符串，遍历栈中剩下的元素:O(n)
空间复杂度分析
最多为n，最小为0。最大空间复杂度为O(n)
源码
class Solution {
public:
int longestValidParentheses(string s) {
if (s.length() == 0) {
return 0;
}
stack<int> indexStack;
stack<char> st;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
st.push(s[i]);
indexStack.push(i);
} else {
if (!st.empty() && st.top() == '(') {
st.pop();
indexStack.pop();
} else {
st.push(s[i]);
indexStack.push(i);
}
}
}
if (st.empty()) {
return s.size();
} else {
int lastIndex = s.length(), beginIndex = 0;
int longest = 0;
while (!indexStack.empty()) {
beginIndex = indexStack.top();
cout << beginIndex << endl;
indexStack.pop();
longest = max(longest, lastIndex - beginIndex - 1);
lastIndex = beginIndex;
}
return max(longest, lastIndex);
}
}
};
