题解 | #最长的括号子串#

思路：

• 用cnt记录左右括号的相对大小，注意必须在cnt等于零的时候才能给maxLen赋值，否则若左括号大于右括号数也不是合法的子串，但若左括号大于右括号，一次遍历无法得出结果，需要从右向左也遍历一次
• 动态规划，dp[i]代表以下标i的元素si结尾的合法子串的最长长度，si若为左括号，则长度为0，只有为右括号才有可能为合法子串，为右括号时，前一个字符分为左括号和右括号两种，为左括号时，即为dp[i-2]+2，为右括号时，判断下标i有无配对的左括号，位置在i-dp[i-1]-1处，若为左括号，还需考虑左括号的前一个是否是连续的子串，即加dp[i-dp[i-1]-2]。
• 栈结构解决，保持栈底元素为当前已经遍历过的元素中最后一个没有被匹配的右括号的下标，栈里其他元素维护左括号的下标，若遇到左括号直接将索引入栈，若为右括号，先弹出栈顶元素，代表已匹配概括号（需要初始化栈时加入-1）：
  • 若栈为空，说明该括号是最后的一个未被匹配的括号，将该索引入栈
  • 若栈不为空，说明被左括号匹配，长度就是当前索引-栈顶索引（不包含栈顶索引的元素，所以初始化时加入-1）

代码：

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
      //用栈解决
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0,len=s.length(); i < len; i++) {
          if (s.charAt(i) == '(') {
            stack.push(i);
          } else {
            stack.pop();
            if (stack.isEmpty()) {
              stack.push(i);
            } else {
              maxans = Math.max(maxans, i - stack.peek());
            }
          }
        }
        return maxans;

//        //动态规划，dp[i]代表以下标i的元素si结尾的合法子串的最长长度，si若为左括号，则长度为0，只有为右括号才有可能为合法子串，
        //为右括号时，前一个字符分为左括号和右括号两种，为左括号时，即为dp[i-2]+2，为右括号时
//		if(s==null||s.length()==0){
//            return 0;
//        }
//        char[] ss=s.toCharArray();
//        int n=ss.length;
//        int[] dp=new int[n+1];
//        int maxLen=0;
//        for(int i=1;i<n;i++){
//            if(ss[i]==')'){
//                if(ss[i-1]=='('){
//                    dp[i]=(i-2>=0?dp[i-2]:0) +2;
//                }else{
//                    if(i-dp[i-1]-1>=0&&ss[i-dp[i-1]-1]=='('){
 //                       dp[i]=dp[i-1]+2+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0);
//                    }
//                }
//                maxLen=Math.max(maxLen,dp[i]);
//            }
//        }
//        return maxLen;
       
//         //用cnt记录左右括号的相对大小，注意必须在cnt等于零的时候才能给maxLen赋值，否则若左括号大于右括号数也不是合法的子串
//         //但若左括号大于右括号，一次遍历无法得出结果，需要从右向左也遍历一次
//         if(s==null||s.length()==0){
//             return 0;
//         }
//         char[] ss=s.toCharArray();
//         int n=ss.length;
//         int maxLen=0;
//         int cnt=-1;//字符串中左右括号的多少的代表，正代表左括号多，负代表右括号多,初始化为负，这样第一个元素的判断即可和后续一样，小于0代表当前元素之前已经存在右括号大于左括号的情况，即若当前是左括号，该位置是后一个子串的开始位置
//         int len=0;
//         for(int i=0;i<n;i++){
//             if(ss[i]=='('){
//                 if(cnt<0){
//                     len=0;
//                     cnt=0;
//                 }
//                     cnt++;
//             }else{
//                 if(cnt>0){
//                     len+=2;
//                 }
//                 cnt--;
//             }
//             if(cnt==0){
//                 maxLen=Math.max(maxLen,len);
//             }
//         }
//         cnt=-1;
//         for(int i=n-1;i>=0;i--){
//             if(ss[i]==')'){
//                 if(cnt<0){
//                     len=0;
//                     cnt=0;
//                 }
//                     cnt++;
//             }else{
//                 if(cnt>0){
//                     len+=2;
//                 }
//                 cnt--;
//             }
//             if(cnt==0){
//                 maxLen=Math.max(maxLen,len);
//             }
//         }
//         return maxLen;
    }
}