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.
思路分析：这题做括号匹配，很容易想到用栈，但是这题栈里面保存括号的index比较好，方便长度计算。基本做法是，遇到左括号入栈，遇到右括号出栈，当进行出栈操作的时候，考虑两种情况
1 当前栈为空，那么没法匹配这个右括号，以该位置的下一个位置i+1为考察括号子串的起点。
2 当前栈不为空，弹出栈顶元素。弹出后如果栈为空，那么合法子串长度是i-start+1;弹出后栈不为空，也就是还有多余的左括号在里面，，那么合法子串长度为从当前栈顶元素下一个元素开始，到i结束，也就是i-(stack.peek()+1)+1 = i – stack.peek()。
对字符串进行一遍扫描，时间复杂度和空间复杂度都是O（n）.
AC Code
public class Solution {public int longestValidParentheses(String s) {//0914if(s == null || s.length() < 2) return 0;char[] sCharArray = s.toCharArray();int n = sCharArray.length;Stack<Integer> stack = new Stack<Integer>();int start = 0;int max = 0;for(int i = 0; i < n; i++){if(sCharArray[i] == ‘(‘){stack.push(i);}else{if(stack.isEmpty()){start = i+1;} else{stack.pop();max = stack.isEmpty()?Math.max(max, i – start +1):Math.max(max, i – stack.peek());}}}return max;//0920}}
只要心中有希望存在，就有幸福存在。
