题目描述： 思路：一开始的想法是和寻找最长回文子串一样做，但是想了想这种方法只能解决(())这种样式的括号，而无法解决()()这样的括号。于是想到了用栈的方法，如果是(就入栈，如果是)且栈不为空则出栈，并减去二者下标。但第一遍编完后出了问题
class Solution { public int longestValidParentheses(String s) { Deque<Integer> deque=new LinkedList (); int max=0; int cur=0; for (int i=0;i<s.length();i++){ if(s.charAt(i)=='('){ deque.push(i); }else{ if(!deque.isEmpty()){ int mid=deque.pop(); cur=i-mid+1; max=max>cur?max:cur; } } } return max; } }这种方法得出的()()这种类型的计算结果都为2，因为没有考虑到这种情况而只解决了(())这种情况。那么如何解决呢？按照官方的思路，出栈后用)对应的下标减去当前栈顶的下标。为了防止前两个字符是()而导致空栈，因此先入栈个-1.
class Solution { public int longestValidParentheses(String s) { Deque<Integer> deque=new LinkedList (); deque.push(-1); int max=0; int cur=0; for (int i=0;i<s.length();i++){ if(s.charAt(i)=='('){ deque.push(i); }else{ deque.pop(); if(!deque.isEmpty()){ cur=i-deque.peek(); max=max>cur?max:cur; }else{ deque.push(i); } } } return max; } }运行结果： 其他想法：1.动态规划 2.左右两次贪心便利 1.动态规划：首先以(结尾的字串均不是有效的，因此其dp数组相应下标的元素为0。因此只需要求出以)为结尾的dp数组值。如果)的前面是(，那么这对括号就是有效的，那么就应该在(前一索引的dp数组上+2。如果)的前面不是(,那么就意味着(())会出现这种情况，那么就需要：(拿官方的话来吧，自己文字功底太有限了，说不明白) 代码：
public class Solution { public int longestValidParentheses(String s) { int maxans = 0; int dp[] = new int[s.length()]; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2; } maxans = Math.max(maxans, dp[i]); } } return maxans; } }2.官方给出的最优的解法是 给出的代码：
public class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, maxlength = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * right); } else if (right > left) { left = right = 0; } } left = right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * left); } else if (left > right) { left = right = 0; } } return maxlength; } }总的来说这种想法个人感觉很奇特。
