【LeetCode】32.最長有効括弧結題報告(C++)
1449 ワード
原題住所:
https://leetcode-cn.com/problems/longest-valid-parentheses/description/
タイトルの説明:
例1:
例2:
https://leetcode-cn.com/problems/longest-valid-parentheses/description/
タイトルの説明:
'('
および')'
のみを含む文字列が与えられ、最も長い有効な括弧を含むサブ列の長さが見出される.例1:
: "(()"
: 2
: "()"
例2:
: ")()())
"
: 4
: "()()"
:
class Solution {
public:
int longestValidParentheses(string s) {
stack stk;
int count = 0;
int max = 0;
int m = 0;
int n = s.size();
int* a = new int[n];
for(int i = 0; i < n; i ++)
a[i] = 0;
for(int i = 0; i < n; i ++){
if(s[i] == '(')
stk.push(m++);
else if(!stk.empty()){
int tmp = stk.top();
stk.pop();
a[tmp] = 1;
}
else
m ++;
}
for(int i = 0; i < s.size(); i ++)
if(a[i] == 1)
count += 2;
else{
if(count > max)
max = count;
count = 0;
}
return max;
}
};