题目描述
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 "()()"
思路分析
首先，这个题的总体思路相当于Valid Parentheses这道题的升级版。括号匹配，肯定会想到用栈，但是这道题不同的是要找到最长的有效括号子串，子串在寻找的过程中你无法确定它是不是有效。
例如()(()，在当前的状态来看是两个有效括号，但是如果继续往后走，有可能是()(())，这样的话两个有效括号就变成了一个。
因此必须能够记录匹配的长度变化，可以采用位置记录。例如()(()，需要同时记录中间(的位置和起始的位置0，虽然当前子串的长度判断是通过和(位置进行差值得到的，但是一旦这个(被匹配掉，就要和起始位置来进行比较。因此，需要一个变量start来记录有效括号的可能的最早的起始位置。
通过start来记录起始位置，
- 如果当前为
(则将位置入栈； - 如果是
)，则判断当前栈：- 如果当前栈为空，说明匹配到了一个无效括号，start从i+1的位置开始
- 如果当前栈不空，说明需要和栈里的
(匹配融合掉，这时再看栈：- 如果栈为空，说明左括号全部匹配掉了，就需要用当前位置i - start + 1来更新结果值（
max(res, i - start + 1)） - 如果栈不空，说明干掉了一个左括号，还有多余的左括号，就将最大值更新到这个左括号的位置，即
max(res, i - stack.peek() + 1)
- 如果栈为空，说明左括号全部匹配掉了，就需要用当前位置i - start + 1来更新结果值（
代码实现
public int longestValidParentheses(String s) {
LinkedList<Integer> stack = new LinkedList<>();
int cnt = 0;
int start = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else if (s.charAt(i) == ')') {
if (stack.isEmpty()) {
start = i + 1;
} else {
stack.pop();
cnt = stack.isEmpty() ? max(cnt, i - start + 1) : max(cnt, i - stack.peek());
}
}
}
return cnt;
}
private int max(int a, int b) {
return a > b ? a : b;
}
