乘风破浪：LeetCode真题_032_Longest Valid Parentheses

一、前言

这也是非常有意思的一个题目，我们之前已经遇到过两个这种括号的题目了，基本上都要用到堆栈来解决，这次最简单的方法当然也不例外。

二、Longest Valid Parentheses

2.1 问题

2.2 分析与解决

通过分析题意，这里我们有几种方法：

暴力算法：

public class Solution {

    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) == '(') {

                stack.push('(');

            } else if (!stack.empty() && stack.peek() == '(') {

                stack.pop();

            } else {

                return false;

            }

        }

        return stack.empty();

    }

    public int longestValidParentheses(String s) {

        int maxlen = 0;

        for (int i = 0; i < s.length(); i++) {

            for (int j = i + 2; j <= s.length(); j+=2) {

                if (isValid(s.substring(i, j))) {

                    maxlen = Math.max(maxlen, j - i);

                }

            }

        }

        return maxlen;

    }

}

但是对于比较长的字符串就会超时了，因为时间复杂度为O(n~3)：

第二种方法：动态规划

我们使用dp[i]表示前面的i个字符的最大有效括号长度，因此dp[0]=0,dp[1]=0,于是就可以开始推出一个公式来计算了。

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;

    }

}

　　　方法三：通过我们的方法，堆栈，很清晰很容易的解决了问题。

public class Solution {

    public int longestValidParentheses(String s) {

        int maxans = 0;

        Stack<Integer> stack = new Stack<>();

        stack.push(-1);

        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) == '(') {

                stack.push(i);

            } else {

                stack.pop();

                if (stack.empty()) {

                    stack.push(i);

                } else {

                    maxans = Math.max(maxans, i - stack.peek());

                }

            }

        }

        return maxans;

    }

}

当然还有其他的方法，在此不再赘述。

三、总结

在我们遇到括号的时候一定要想到使用堆栈来解决，当然动态规划是比较难的，我们也要理解和使用。

巴特西

乘风破浪：LeetCode真题_032_Longest Valid Parentheses

乘风破浪：LeetCode真题_032_Longest Valid Parentheses

一、前言

二、Longest Valid Parentheses

2.1 问题

2.2 分析与解决

三、总结

最新文章

热门文章