【LeetCode】32.最長有効括弧結題報告(C++)

1449 ワード

原題住所:
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;
    }
};