最后一遍-L32-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：再次想到了DP
思路2：突然想到滑动窗口
思路1：
/**
* 栈中存储的竟然是下标值，这个比较的不容易想到
* 1. 首先理解题意是关键的步骤：挑选可以使用的括号规则，如下的规则
*
* ()(() 计算值为2
* ()()) 计算值为4
*
* 2. 理解了题意之后，就是梳理具体的逻辑
*
* 采用栈的的数据结构，来匹配右括号与左括号的匹配的规则
* 左括号则入栈，右括号需要处理的逻辑是：
* 匹配或者不匹配的情况
*
* 如果是匹配的情况，那么需要把匹配的左括号出栈，然后根据出栈后的情况：
* 如果还有内容，没有匹配完呢，直接的更新数据。
* 如果栈内没有了内容，需要计算最大的长度。
*
* 如果是不匹配的情况，右括号不匹配的情况，就是直接的丢弃。判断这个时候的栈内元素为空，并且更新最大长度的开始的值。
*
* */
具体的代码：
public class L32 {
public static void main(String[] args) {
System.out.println(longestValidParentheses("(")); //0
System.out.println(longestValidParentheses("()")); //2
System.out.println(longestValidParentheses("()(()")); //2
System.out.println(longestValidParentheses("()()")); //4
System.out.println(longestValidParentheses(")()())"));//4
System.out.println(longestValidParentheses("()(()")); //2
System.out.println(longestValidParentheses(")()())"));//4
}
/**
* ()()),
* ()((),
* (()((),
* ((()
* */
public static int longestValidParentheses(String s){
Stack<Integer> st = new Stack<Integer>();
Integer left = null;
int max=0;
for (int i = 0; i < s.length(); i++) {
Character si = s.charAt(i);
if('(' == si) {
st.push(i);
}else{
// 如果这个时候的stack为null，说明)为一段开局的字符，或者初始化的字符
if(st.isEmpty()){
left=i;
}else{
st.pop();// 说明匹配到一个字符，没有pop前，栈顶元素是(,对应的index是stack.peek, 当前的index=i
if(st.isEmpty()) {
//如果此时栈内为null，说明已经匹配到了一个可以计算的【完美一段括号字符串】，例如(),或者(())
if(left == null){ //如果left为null，说明一直是【完美一段括号字符串】
max = i+1;
}else{
max = Math.max(max,i-left);
}
}else{
//如果这个时候，栈内还有元素，就是栈内就是对应(((的index，仍然需要计算一个短的【完美一段括号字符串】
max = Math.max(max,i-st.peek());
}
}
}
}
return max;
}
}