练手系列(2) 最长有效括号的长度详解编程语言

这是厐果网英雄会（IT虾米网）上的一道题。

原题如下：给定只包含括号字符( 和 ) 的字符串，请找出最长的有效括号内子括号的长度。

举几个例子如下： 例如对于 ( () ，最长的有效的括号中的子字符串是 () ，有效双括号数1个，故它的长度为 2。  再比如对于字符串 ) () () ) ，其中最长的有效的括号中的子字符串是 () () ，有效双括号数2个，故它的长度为4。  再比如对于 ( () () ) ，它的长度为6。        

换言之，便是有效双括号 () 数的两倍。

给定函数原型int longestValidParentheses(string s)，请完成此函数，实现上述功能。 

看到题目立马想到用栈来实现。Java的集合类Vector正好有一个子类Stack，所以就直接拿来用了。

过程先用图片表示一下

 再用代码表示：

 1 import java.util.Stack; 

 3 public class Test01 { 

 4 public static void main(String[] args) { 

 5 int i = longestValidParentheses(")()(()()"); 

 6 System.out.println(i); 

 7 } 

 9 public static int longestValidParentheses(String s) { 

10 // 定义子括号的长度 

11 int j = 0; 

12 // 将字符串还原为字符数组 

13 char[] chs = s.toCharArray(); 

14 // 创建一个Stack实例 

15 Stack stack = new Stack(); 

16 // 遍历字符数组 

17 for (int i = 0; i chs.length; i++) { 

18 // 如果这个数组元素是右括号，那么就看看栈里面是不是已经有了左括号 

19 if (chs[i] == )) { 

20 // 如果栈里面为空，那么丢弃这个右括号，找下一个数组元素 

21 if (stack.size() 0 stack.peek() == null) { 

22 continue; 

23 } else if (stack.size() 0 

24 (stack.peek().toString()).equals("(")) { 

25 // 如果栈里面有一个左括号，那么弹出此左括号，并把长度加上1 

26 stack.pop(); 

27 j++; 

28 } 

29 } else { 

30 // 如果为左括号，那么直接压入栈 

31 stack.push(chs[i]); 

32 } 

33 } 

34 return j * 2; 

35 } 

36 }

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/19426.html