思路1：利用栈来做括号匹配的问题(栈中存储下标而非括号，因为我们可以用下标来找到括号)，每当遇到无法匹配的括号时，我们记录他们之间的距离（下标之间的差 - 1），最大的距离就是解。

solution1：Use a stack to do bracket-matching(instead of storing bracket, we store index since we could use index to index the bracket), each time we can't match two brackets, we record their distence(the difference between two indexes), the max distence is the solution.

for example:

```
s = "(()(", max = 0, dif = 0 // max is the result, dif is the distence of two mismacth bracket
step 0: stack = []
i = 0, s[i] = '(' // i is the index we currently process
step 1: stack = [0] // s.charAt(0) = '(', we store index of '('
i = 1, s[i] = '(' dif = i - stack.peek() - 1 = 0 // mismatch of s[stack.peek()] and s[i]
max = Math.max(max, dif) = 0
step 2: stack = [0, 1]
i = 2, s[i] = ')' stack.pop() // match of s[stack.peek()] and s[i]
step 3: stack = [0]
i = 3, s[i] = '(' dif = i - stack.peek() - 1 = 2 // mismatch of s[stack.peek()] and s[i]
max = Math.max(max, dif) = 2
step 4: ...
```

```
public class Solution {
public int longestValidParentheses(String s) {
Deque<Integer> stack = new ArrayDeque<>(s.length());
if(s == null) return 0;
int max = 0;
stack.push(-1); // 用一个哨兵， as a guard
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ')' && stack.size() != 1 && s.charAt(stack.peek()) == '(') { // match
stack.pop();
} else { // mismatch
max = Math.max(max, i - stack.peek() - 1);
stack.push(i);
}
}
return Math.max(max, s.length() - stack.pop() - 1);
}
}
```