Longest Valid Parentheses leetcode java-最长有效括号（非动态规划解法）

淡淡的烟草味﹌ 2023-06-22 07:23 124阅读 0赞

Longest Valid Parentheses leetcode java  
题目：

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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

题解：

思路一：

使用栈的方式。

时间复杂度 O(n)，空间复杂度 O(n)

题解引用自：http://codeganker.blogspot.com/2014/03/longest-valid-parentheses-leetcode.html

这道题是求最长的括号序列，比较容易想到用栈这个数据结构。基本思路就是维护一个栈，遇到左括号就进栈，遇到右括号则出栈，并且判断当前合法序列是否为最 长序列。不过这道题看似思路简单，但是有许多比较刁钻的测试集。具体来说，主要问题就是遇到右括号时如何判断当前的合法序列的长度。比较健壮的方式如下：  
(1) 如果当前栈为空，则说明加上当前右括号没有合法序列（有也是之前判断过的）；  
(2) 否则弹出栈顶元素，如果弹出后栈为空，则说明当前括号匹配，我们会维护一个合法开始的起点start，合法序列的长度即为当前元素的位置 -start+1；否则如果栈内仍有元素，则当前合法序列的长度为当前栈顶元素的位置下一位到当前元素的距离，因为栈顶元素后面的括号对肯定是合法的，而 且左括号出过栈了。  
因为只需要一遍扫描，算法的时间复杂度是O(n)，空间复杂度是栈的空间，最坏情况是都是左括号，所以是O(n)。

然后网上找了解法，有些人使用了DP，我没仔细看。。主要还是吸取了栈的思想。代码引用自：http://rleetcode.blogspot.com/2014/01/longest-valid-parentheses.html, 个人稍作修改。

如下所示：

1      public static int longestValidParentheses(String s) \{  
 2         if (s==null||s.length()==0)\{  
 3             return 0;  
 4             \}  
 5           
 6         int start=0;  
 7         int maxLen=0;  
 8         Stack<Integer> stack=new Stack<Integer>();  
 9           
10         for (int i=0; i<s.length();i++)\{  
11             if (s.charAt(i)=='(')\{  
12                 stack.push(i);  
13             \}else\{  
14                 if (stack.isEmpty())\{  
15                     // record the position before first left parenthesis  
16                     start=i+1;  
17                 \}else\{  
18                     stack.pop();  
19                     // if stack is empty mean the positon before the valid left parenthesis is "last"  
20                     if (stack.isEmpty())\{  
21                         maxLen=Math.max(i-start+1, maxLen);  
22                     \}  
23                     else\{  
24                         // if stack is not empty, then for current i the longest valid parenthesis length is  
25                         // i-stack.peek()  
26                         maxLen=Math.max(i-stack.peek(),maxLen);  
27                     \}  
28                 \}  
29             \}  
30         \}  
31             return maxLen;  
32             \}

动态规划解法可参考：

# [LeetCode-32.最长有效括号（考察点：栈/动态规划）][LeetCode-32.]： #

[https://zhuanlan.zhihu.com/p/41951874][LeetCode-32.]

[LeetCode-32.]: https://zhuanlan.zhihu.com/p/41951874