LeetCode - 32. Longest Valid Parentheses

本文主要是介绍LeetCode - 32. Longest Valid Parentheses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

32. Longest Valid Parentheses

Problem's Link

----------------------------------------------------------------------------

Mean:

给定一个由'('和')'组成的字符串，求最长连续匹配子串长度.

analyse:

定义一个stack<pair<char,int>>类型的stack.

遇到'('进栈;

遇到')'需要分两种情况讨论：

栈顶元素为'('，正好匹配，将栈顶元素出栈;
栈顶元素为')'或栈为空，将当前符号和下标入栈.

这个栈构建完以后，我们只需要找这个栈中相邻两个top.second()之差即可.

trick：注意'(()'这种情况，需要特判，即backVal的值为len.

Time complexity: O(N)

view code

 /** 
  * ----------------------------------------------------------------- 
  * Copyright (c) 2016 crazyacking.All rights reserved. 
  * ----------------------------------------------------------------- 
  *       Author: crazyacking 
  *       Date  : 2016-03-01-20.35 
  */ 
 #include <queue> 
 #include <cstdio> 
 #include <set> 
 #include <string> 
 #include <stack> 
 #include <cmath> 
 #include <climits> 
 #include <map> 
 #include <cstdlib> 
 #include <iostream> 
 #include <vector> 
 #include <algorithm> 
 #include <cstring> 
 using namespace std; 
 typedef long long( LL); 
 typedef unsigned long long( ULL); 
 const double eps( 1e-8); 
 
 class Solution 
 { 
 public : 
     int longestValidParentheses( string s) 
     { 
         int len =s . length(); 
         stack < pair < char , int >> sta; 
         for( int i = 0; i < len; ++ i) 
         { 
             if(s [ i ] == '(') 
                 sta . push( make_pair( '(' , i)); 
             else 
             { 
                 if( ! sta . empty()) 
                 { 
                     pair < char , int > t = sta . top(); 
                     if( t . first == '(') 
                         sta . pop(); 
                     else 
                         sta . push( make_pair( ')' , i)); 
                 } 
                 else 
                     sta . push( make_pair( ')' , i)); 
             } 
         } 
 
         int ans = 0 , frontVal = len , backVal; 
         if( ! sta . empty() && sta . top (). second != len - 1) 
             backVal = len; 
         else 
             backVal = len - 1; 
         while( ! sta . empty()) 
         { 
             pair < char , int > t = sta . top(); 
             sta . pop(); 
             frontVal = t . second; 
             ans = max( ans , backVal - frontVal - 1); 
             backVal = frontVal; 
         } 
         ans = max( ans , frontVal - 0); 
         return ans; 
     } 
 }; 
 
 int main() 
 { 
     Solution solution; 
     string s; 
     while( cin >>s) 
     { 
         cout << solution . longestValidParentheses(s) << endl; 
     } 
     return 0; 
 } 
 /* 
 
 */ 