LeetCode每日一题（题32）

题目

题目：https://leetcode-cn.com/problems/longest-valid-parentheses/
题目大意：给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
分析：这道题目比较有意思，虽然标注的是困难的题目，但是代码并不长，虽然我第一时间也没做出来 。
一般地可以采用动态规划，或者单调栈两种方式来做，主要还是因为看到最长子串的题目总是会想到动态规划，看到括号的题目就容易想到栈，所以就按照这两种方式来做吧。

动态规划

前天我们写了有关于动态规划的模板，首先第一层状态肯定毫无疑问是当前字符的下标，这里考虑一下当前字符的可能：
如果当前字符是’(‘那么就不可能组成有效括号，所以当前有效括号的长度为0,。
如果当前字符是’)‘那么查看一下前面一个字符是否是’(’，如果是的话说明这两个字符可以组成一个有效括号，那么当前子串的长度就依赖于dp[i-2]处的长度。
但是如果前面一个字符是’)’，那么情况就有一些麻烦了。
考虑一下字符串"(())"，对于最后一个右括号来说正好满足我们正在考虑的情况，这里的dp[i-1]的值是2，意味着前面2个字符恰好组成一个有效子串，所以我们需要看s[i-dp[i-1]-1]位置处的字符，如果字符是’('那么恰好可以组成一个有效字符，从s[i-dp[i-1]-1]到s[i]就是一个有效子串，这个时候的长度依赖于谁呢？注意不是dp[i-2]而是dp[i-dp[i-1]-2]处的长度。
也就是说我们的长度总是依赖于判断是否是左括号字符的前面一个字符处的长度。
所以可以写出状态转移方程，注意判断是否越界。
dp[i] = i>=2?dp[i-2]+2:2 s[i] == ')'&&s[i-1]=='('
dp[i] = i>=dp[i-1]+2?dp[i-dp[i-1]-2]+2:2 s[i] == ')' && s[i-dp[i-1]-1] == '('
dp[i] = 0 s[i] == '(' 其他

class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0)
            return 0;
        int[] dp = new int[s.length()];
        dp[0] = 0;
        int max = 0;
        for(int i=1;i<dp.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] && 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;
                }
            }
            max = Math.max(dp[i],max);
        }
        return max;
    }
}

单调栈

采用单调栈的话要考虑的东西会稍微少一些。
每次把左括号入栈，然后右括号入栈的时候判断一下是否有左括号需要出栈，如果有的话，则把左括号出栈，然后记录一下和栈顶元素的距离，这就是当前有效子串长度，这个时候右括号也不需要入栈了，因为它对后面的元素不会产生影响。
没有的话，说明不是有效括号，直接入栈。
为了方便栈为空的情况，我们在栈中先压入一个下标为-1的元素，这样就不需要讨论栈为空的特殊情况。

class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0)
            return 0;
        Deque<Integer> stack = new LinkedList<>();
        int max = 0;
        stack.addLast(-1);
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == '('){
                stack.addLast(i);   
            }
            else{
                if(stack.peekLast() != -1 && s.charAt(stack.peekLast()) == '('){
                    stack.removeLast();
                    max = Math.max(max,i-stack.peekLast());
                }
                else{
                    stack.addLast(i);
                }
            }
        }
        return max;
    }
}