Description
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example
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.思路
- 用一个栈，将有效的括号匹配表示到一个标志数组中
- 然后变量标志数组，找到最大长度
代码
class Solution {
public:
int longestValidParentheses(string s) {
int len = s.size();
if(len <= 1) return 0;
stack<int> Stack;
vector<bool> flag(len, false);
int i = 0, maxLen = 0, tmpLen = 0;
while(i < len){
if(s[i] == '('){
Stack.push(i);
i++;
}
else{
if(Stack.empty()){
i++;
continue;
}
flag[i] = true;
flag[Stack.top()] = true;
Stack.pop();
i++;
}
}
for(i = 0; i < len; ++i){
if(flag[i])
tmpLen++;
else{
if(tmpLen > maxLen)
maxLen = tmpLen;
tmpLen = 0;
}
}
if(tmpLen > maxLen)
maxLen = tmpLen;
return maxLen;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
