[LeetCode] 32. 最长有效括号

题目链接 : https://leetcode-cn.com/problems/longest-valid-parentheses/

题目描述:

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例:

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

思路:

常规思路1:

对于这种括号匹配问题,一般都是使用栈

我们先找到所有可以匹配的索引号,然后找出最长连续数列!

例如:s = )(()()) ,我们用栈可以找到,

位置2和位置3匹配,

位置4和位置5匹配,

位置1和位置6匹配,

这个数组为:2,3,4,5,1,6这是通过栈找到的,我们按递增排序!1,2,3,4,5,6

找出该数组的最长连续数列的长度就是最长有效括号长度!

所以时间复杂度来自排序:O(nlogn)

接下来我们思考,是否可以在省略排序的过程,在弹栈时候进行操作!

直接看代码理解!所以时间复杂度为:O(n)

思路2:

dp方法:

我们用dp[i]表示以i结尾的最长有效括号;

当s[i] 为(,dp[i] 必然等于0,因为不可能组成有效的括号;
那么s[i] 为)

2.1 当s[i-1] 为(,那么dp[i] = dp[i-2] + 2;

2.2 当s[i-1] 为)并且 s[i-dp[i-1] - 1]为(,那么dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2];

时间复杂度:(O(n))

关注我的知乎专栏,了解更多解题技巧,大家共同进步!

代码:

思路一:

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        res = []
        stack = []
        for i in range(len(s)):
            if stack and s[i] == ")":
                res.append(stack.pop())
                res.append(i)
            if s[i] == "(":
                stack.append(i)
        res.sort()
        #print(res)
        i = 0
        ans = 0
        n = len(res)
        while i < n:
            j = i
            while j < n - 1 and res[j + 1] == res[j] + 1:
                j += 1
            ans = max(ans, j - i + 1)
            i = j + 1
        return ans

优化:

python

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        res = 0
        stack = [-1]
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    res = max(res,i - stack[-1])
        return res

java

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        //System.out.println(stack);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') stack.push(i);
            else {
                stack.pop();
                if (stack.isEmpty()) stack.push(i);
                else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }
}

思路2:dp

python

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0: return 0
        dp = [0] * n
        res = 0
        for i in range(n):
            if i>0 and s[i] == ")":
                if  s[i - 1] == "(":
                    dp[i] = dp[i - 2] + 2
                elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
                if dp[i] > res:
                    res = dp[i]
        return res

java

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;
        int[] dp = new int[s.length()];
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] + 2 : 2);
                } else if (s.charAt(i - 1) == ')' && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}