Longest Valid Parentheses

标签（空格分隔）： leetcode 算法

---

题目

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.

“()(()”, which has length = 2.

解答

就是要求最长连续的匹配的括号数

class Solution { public: int longestValidParentheses(string s) { //先将匹配或不匹配的标记打入matchV中 stack<size_t> posStack; vector<bool> matchV(s.size()); for (string::size_type i = 0; i < s.size(); ++i) { if(s[i] == '(') { posStack.push(i); } else { if (posStack.size()) { matchV[posStack.top()] = true; posStack.pop(); matchV[i] = true; } } } //求连续的最长匹配数目 size_t maxLen = 0; size_t nowLen = 0; for (string::size_type i = 0; i < matchV.size(); ++i) { if (matchV[i]) { ++nowLen; if (nowLen > maxLen) { maxLen = nowLen; } } else { nowLen = 0; } } return maxLen; } };