本文共 2204 字，大约阅读时间需要 7 分钟。

class Solution {//once meet Parentheses, we should think of stack//then it is some thing trivialpublic:	int longestValidParentheses(string s) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		stack
   
    
     > charStack;		vector
     
       valid(s.size(), false);		for (int i = 0; i < s.size(); ++i)		{			if ( !charStack.empty() )			{				char topChar = charStack.top().first;				int topPos = charStack.top().second;				if( topChar == '(' && s[i] == ')')				{					charStack.pop();					for (int j = topPos; j <= i; ++j)						valid[j] = true;				}				else charStack.push(make_pair(s[i], i));			}			else charStack.push(make_pair(s[i], i));		}		//then count the longest length		int nowLen = 0;		int maxLen = 0;		for (int i = 0; i < s.size(); ++i)		{			if(valid[i])				nowLen++;			else 			{				maxLen = max(maxLen, nowLen);				nowLen = 0;			}		}		maxLen = max(maxLen, nowLen);//note here, then end of the string		return maxLen;	}};
     
    
   

second time

class Solution {//DP based solution need O(n^3)//stack based solution need O(n^2)public:    struct Node    {        char c;        int pos;        Node(char _c, int _pos):c(_c),pos(_pos){};    };    int longestValidParentheses(string s) {        // Start typing your C/C++ solution below        // DO NOT write int main() function       stack
   
     charStack;       vector
    
      pLen(s.size(), 0);       for(int i = 0; i < s.size(); ++i)       {           if(s[i] == '(') charStack.push(Node(s[i], i));           else           {               if(!charStack.empty() && charStack.top().c == '(')               {                   int pos = charStack.top().pos;                   pLen[pos] = i-pos+1;                   charStack.pop();               }               else charStack.push(Node(s[i], i));           }       }       //get maxlen       int maxLen = 0;       for(int i = 0; i < s.size(); ++i)       {           int curLen = 0;           int nextPos = i;           while(nextPos < s.size() && pLen[nextPos] != 0)           {               curLen += pLen[nextPos];               nextPos = pLen[nextPos]+nextPos;           }           maxLen = max(maxLen, curLen);       }              return maxLen;    }};
    
   

转载地址：http://tlxti.baihongyu.com/