题目
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
思路
道题是求最长的括号序列，比较容易想到用栈这个数据结构。基本思路就是维护一个栈，遇到左括号就进栈，遇到右括号则出栈，并且判断当前合法序列是否为最长序列。不过这道题看似思路简单，但是有许多比较刁钻的测试集。具体来说，主要问题就是遇到右括号时如何判断当前的合法序列的长度。比较健壮的方式如下：
(1) 如果当前栈为空，则说明加上当前右括号没有合法序列（有也是之前判断过的）；
(2) 否则弹出栈顶元素，如果弹出后栈为空，则说明当前括号匹配，我们会维护一个合法开始的起点start，合法序列的长度即为当前元素的位置-start+1；否则如果栈内仍有元素，则当前合法序列的长度为当前栈顶元素的位置下一位到当前元素的距离，因为栈顶元素后面的括号对肯定是合法的，而且左括号出过栈了。
因为只需要一遍扫描，算法的时间复杂度是O(n)，空间复杂度是栈的空间，最坏情况是都是左括号，所以是O(n)。
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int longestValidParentheses(string s) {
if (s.empty()) return 0;
stack<int> index;
int maxCount = 0, startIndex = 0;
for (int i = 0; i < s.length(); i++)
{
if (s.at(i) == '(') index.push(i);
else
{
if (index.empty()) startIndex = i + 1;
else
{
index.pop();
if (index.empty()) maxCount = max(maxCount, i - startIndex + 1);
else { maxCount = max(maxCount, i - index.top()); }
}
}
}
return maxCount;
}
};
int main(int argc, char* argv[])
{
string s = ")()())";
auto res = Solution().longestValidParentheses(s);
return 0;
}
