[leetcode]32. Longest Valid Parentheses最长合法括号子串

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"

 

题意：

给定一个括号序列，找出最长的合法括号子串。

 

 

Solution1:  Two pointers(fast&slow)  + Stack

It's just like using [start+1...i] to maintain a window where contains longest valid parentheses

 

 

 

code:

1 /* 2 Time: O(n). We traverse the given input 3 Space: O(n). Worse case, input is all contained '（'， then there will be n chars stored in the stack 4 */ 5 class Solution { 6 public int longestValidParentheses(String s) { 7 int result = 0; 8 int start = -1; 9 Stack<Integer> stack = new Stack<>(); // index of every char 10 11 for(int i = 0; i < s.length(); i++){ 12 char c = s.charAt(i); 13 if(c == '('){ 14 stack.push(i); 15 }else if( c == ')'){ 16 if(stack.isEmpty()){ 17 // no matching left '( ' 18 start = i; 19 }else{ 20 stack.pop(); 21 if(stack.isEmpty()){ 22 result = Math.max(result, i - start); 23 }else{ 24 result = Math.max(result, i - stack.peek()); 25 } 26 } 27 } 28 } 29 return result; 30 } 31 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/9206903.html