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.
本題的主要思路就是標記那些括號是被匹配的。
我們可以利用一個布爾數組，如果位置為i的值為true，則表示第i個括號是被匹配的，然后我們只需要求連續為true的元素的個數即可。實現代碼如下：
1 public class LongestValidParentheses {
2 public int longestValidParentheses(String s) {
3 int length = s.length();
4 if (length == 0)
5 return 0;
6 int left = 0;
7 Stack<Integer> indexs = new Stack<Integer>();
8 boolean[] record = new boolean[length];
9 for (int i = 0; i < length; i++) {
10 if (s.charAt(i) == '(') {
11 left++;
12 indexs.push(i);
13 } else if (left > 0) {
14 int idx = indexs.pop();
15 record[idx] = true;
16 record[i] = true;
17 left--;
18 }
19 }
20 int ret = 0;
21 int current = 0;
22 for (int k = 0; k < length; k++) {
23 if (record[k]) {
24 current++;
25 } else {
26 ret = current > ret ? current : ret;
27 current = 0;
28 }
29 }
30 return ret > current ? ret : current;
31 }
32 }