32. Longest Valid Parentheses
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 "()()"
一个只有“（”与“）”的字符串，找到最长的成对的子串。
算法3（无重复子串）、算法5（回文子串）都是找子串的，对于字符串的算法，都离不开遍历。
思路一，暴力遍历。在算法20中，也是求符号是否成对，其中一个思路是用一个stack记录遍历过的符号，利用stack先进后出的特性，与后面的符号进行配对。在这道题中也适用，但是这道题求最长的一个，所以暴力遍历出所有的子串，然后分别去判断是否合法，记录最长的长度。空间复杂度最坏情况下，需要装n-1个符号，即n-1个符号都相同，那么空间复杂度为O(n)。时间复杂度，遍历出所有子串为O(n2)，判断是否合法再乘以n，故为O(n3)。
思路二：
也是使用stack去判断是否配对，但是没必要遍历出全部子串。题目要求一个配对返回长度2，我们先把-1加入到栈中，遍历字符串，如果是左括号，把位置i加入到stack中。如果遇到右括号，stack出栈一位，如果此时stack为空，表示不合法；使用i - stack.pop() ，就是当前配对的长度。为了计算后续是否配对，需要再将当前位置i入栈。这个算法的话，只需要遍历一次，故时间复杂度为O(n)。最坏的空间复杂度为O(n)，原因与思路一相同。
以下为代码：
public int longestValidParentheses(String s) {
int maxLen = 0;
Stack<Integer> stack = new Stack<Integer>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if('(' == s.charAt(i)) {
stack.push(i);
} else {
stack.pop();
if(stack.isEmpty()) {// 这种情况肯定不合法
stack.push(i);
} else {// 配上对了
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
