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.
這題就是求最長的匹配成功的括號(hào)個(gè)數(shù)讶迁。
右括號(hào)會(huì)和前邊最近的左括號(hào)進(jìn)行匹配。把左括號(hào)壓棧若未，就是和棧頂?shù)钠ヅ洹Ｓ靡粋€(gè)和string一樣長的vector去標(biāo)記每個(gè)括號(hào)是否匹配成功步脓。遍歷整個(gè)string膳音，左括號(hào)就把括號(hào)的下標(biāo)壓進(jìn)去，要是右括號(hào)就進(jìn)行匹配骑疆，匹配成功敛滋，返回的匹配成功的左括號(hào)的下標(biāo)许布，并把這對(duì)左括號(hào)和右括號(hào)分別標(biāo)記為1。匹配失敗標(biāo)志位是0不用動(dòng)绎晃，接著往下走蜜唾。
一遍匹配之后就數(shù)最長的連續(xù)的1有多少個(gè)杂曲。
建個(gè)變量保存最大值。用一個(gè)變量當(dāng)計(jì)數(shù)器袁余，多一個(gè)1就加1擎勘，遇到0就把計(jì)數(shù)器清0。最大值就是結(jié)果颖榜。
代碼如下：
class Solution {
public:
int longestValidParentheses(string s) {
int len = s.size();
vector<int> flag(len,0);
vector<int> indexs;
for(int i = 0; s[i] != '\0'; i++)
{
if(s[i] == '(')//左括號(hào)壓索引
indexs.push_back(i);
else if(s[i] == ')')
{
int r = pipei(indexs);
if(r == -1)
flag[i] = 0;
else
{
flag[i] = 1;
flag[r] = 1;
}
}
}
int count = 0;
int maxValue = 0;
for(int i = 0;i< flag.size();i++)
{
if(flag[i] == 0)
count=0;
else
{
count++;
if(maxValue < count)
maxValue = count;
}
}
return maxValue;
}
private:
//成功返回匹配的索引 不成功返回-1
int pipei(vector<int> &indexs)
{
if(indexs.size() == 0)
return -1;
int res = indexs[indexs.size()-1];
indexs.pop_back();
return res;
}
};
