32-最长有效括号(Longest Valid Parentheses)
发表于：2021-12-03 | 分类： 困难
字数统计: 187 | 阅读时长: 1分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/longest-valid-parentheses

英文原文

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

 

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

 

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

中文题目

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

 

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

 

提示：

  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ')'

通过代码

高赞题解

📺视频题解

32.最长有效括号.mp4

📖文字题解

方法一：动态规划

思路和算法

我们定义 $\textit{dp}[i]$ 表示以下标 $i$ 字符结尾的最长有效括号的长度。我们将 $\textit{dp}$ 数组全部初始化为 $0$ 。显然有效的子串一定以 $\text{‘)’}$ 结尾，因此我们可以知道以 $\text{‘(’}$ 结尾的子串对应的 $\textit{dp}$ 值必定为 $0$ ，我们只需要求解 $\text{‘)’}$ 在 $\textit{dp}$ 数组中对应位置的值。

我们从前往后遍历字符串求解 $\textit{dp}$ 值，我们每两个字符检查一次：

  1. $s[i] = \text{‘)’}$ 且 $s[i - 1] = \text{‘(’}$，也就是字符串形如 $“……()”$，我们可以推出：
    $$
    \textit{dp}[i]=\textit{dp}[i-2]+2
    $$
    我们可以进行这样的转移，是因为结束部分的 “()” 是一个有效子字符串，并且将之前有效子字符串的长度增加了 $2$ 。

  2. $s[i] = \text{‘)’}$ 且 $s[i - 1] = \text{‘)’}$，也就是字符串形如 $“……))”$，我们可以推出：
    如果 $s[i - \textit{dp}[i - 1] - 1] = \text{‘(’}$，那么
    $$
    \textit{dp}[i]=\textit{dp}[i-1]+\textit{dp}[i-\textit{dp}[i-1]-2]+2
    $$

我们考虑如果倒数第二个 $\text{‘)’}$ 是一个有效子字符串的一部分（记作 $sub_s$），对于最后一个 $\text{‘)’}$ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 $\text{‘(’}$ ，且它的位置在倒数第二个 $\text{‘)’}$ 所在的有效子字符串的前面（也就是 $sub_s$ 的前面）。因此，如果子字符串 $sub_s$ 的前面恰好是 $\text{‘(’}$ ，那么我们就用 $2$ 加上 $sub_s$ 的长度（$\textit{dp}[i-1]$）去更新 $\textit{dp}[i]$。同时，我们也会把有效子串 $“(sub_s)”$ 之前的有效子串的长度也加上，也就是再加上 $\textit{dp}[i-\textit{dp}[i-1]-2]$。

最后的答案即为 $\textit{dp}$ 数组中的最大值。

<fig1,fig2,fig3,fig4,fig5,fig6,fig7,fig8>

[sol1-Java]
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;
    }
}
[sol1-C++]
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0, n = s.length();
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = max(maxans, dp[i]);
            }
        }
        return maxans;
    }
};
[sol1-C]
int longestValidParentheses(char* s) {
    int maxans = 0, n = strlen(s);
    if (n == 0) return 0;
    int dp[n];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] +
                        ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxans = fmax(maxans, dp[i]);
        }
    }
    return maxans;
}
[sol1-Golang]
func longestValidParentheses(s string) int {
    maxAns := 0
    dp := make([]int, len(s))
    for i := 1; i < len(s); i++ {
        if s[i] == ')' {
            if s[i-1] == '(' {
                if i >= 2 {
                    dp[i] = dp[i - 2] + 2
                } else {
                    dp[i] = 2
                }
            } else if i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(' {
                if i - dp[i - 1] >= 2 {
                    dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
                } else {
                    dp[i] = dp[i - 1] + 2
                }
            }
            maxAns = max(maxAns, dp[i])
        }
    }
    return maxAns
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

复杂度分析

  • 时间复杂度： $O(n)$，其中 $n$ 为字符串的长度。我们只需遍历整个字符串一次，即可将 $\textit{dp}$ 数组求出来。

  • 空间复杂度： $O(n)$。我们需要一个大小为 $n$ 的 $\textit{dp}$ 数组。

方法二：栈

思路和算法

撇开方法一提及的动态规划方法，相信大多数人对于这题的第一直觉是找到每个可能的子串后判断它的有效性，但这样的时间复杂度会达到 $O(n^3)$，无法通过所有测试用例。但是通过栈，我们可以在遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性，同时能得到最长有效括号的长度。

具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

  • 对于遇到的每个 $\text{‘(’}$ ，我们将它的下标放入栈中
  • 对于遇到的每个 $\text{‘)’}$ ，我们先弹出栈顶元素表示匹配了当前右括号：
    • 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    • 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

我们从前往后遍历字符串并更新答案即可。

需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 $-1$ 的元素。

<ppt1,ppt2,ppt3,ppt4,ppt5,ppt6,ppt7,ppt8,ppt9,ppt10,ppt11>

[sol2-Java]
class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        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 {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}
[sol2-C++]
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    maxans = max(maxans, i - stk.top());
                }
            }
        }
        return maxans;
    }
};
[sol2-C]
int longestValidParentheses(char* s) {
    int maxans = 0, n = strlen(s);
    int stk[n + 1], top = -1;
    stk[++top] = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            stk[++top] = i;
        } else {
            --top;
            if (top == -1) {
                stk[++top] = i;
            } else {
                maxans = fmax(maxans, i - stk[top]);
            }
        }
    }
    return maxans;
}
[sol2-Golang]
func longestValidParentheses(s string) int {
    maxAns := 0
    stack := []int{}
    stack = append(stack, -1)
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, i)
        } else {
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                stack = append(stack, i)
            } else {
                maxAns = max(maxAns, i - stack[len(stack)-1])
            }
        }
    }
    return maxAns
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

复杂度分析

  • 时间复杂度： $O(n)$，$n$ 是给定字符串的长度。我们只需要遍历字符串一次即可。

  • 空间复杂度： $O(n)$。栈的大小在最坏情况下会达到 $n$，因此空间复杂度为 $O(n)$ 。

方法三：不需要额外的空间

思路和算法

在此方法中，我们利用两个计数器 $\textit{left}$ 和 $\textit{right}$ 。首先，我们从左到右遍历字符串，对于遇到的每个 $\text{‘(’}$，我们增加 $\textit{left}$ 计数器，对于遇到的每个 $\text{‘)’}$ ，我们增加 $\textit{right}$ 计数器。每当 $\textit{left}$ 计数器与 $\textit{right}$ 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 $\textit{right}$ 计数器比 $\textit{left}$ 计数器大时，我们将 $\textit{left}$ 和 $\textit{right}$ 计数器同时变回 $0$。

这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。

解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：

  • 当 $\textit{left}$ 计数器比 $\textit{right}$ 计数器大时，我们将 $\textit{left}$ 和 $\textit{right}$ 计数器同时变回 $0$
  • 当 $\textit{left}$ 计数器与 $\textit{right}$ 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串

这样我们就能涵盖所有情况从而求解出答案。

<f1,f2,f3,f4,f5,f6,f7,f8,f9,f10,f11,f12,f13,f14,f15,f16,f17>

[sol3-Java]
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;
    }
}
[sol3-C++]
class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = (int)s.length() - 1; i >= 0; i--) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
};
[sol3-C]
int longestValidParentheses(char* s) {
    int n = strlen(s);
    int left = 0, right = 0, maxlength = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            maxlength = fmax(maxlength, 2 * right);
        } else if (right > left) {
            left = right = 0;
        }
    }
    left = right = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            maxlength = fmax(maxlength, 2 * left);
        } else if (left > right) {
            left = right = 0;
        }
    }
    return maxlength;
}
[sol3-Golang]
func longestValidParentheses(s string) int {
    left, right, maxLength := 0, 0, 0
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            left++
        } else {
            right++
        }
        if left == right {
            maxLength = max(maxLength, 2 * right)
        } else if right > left {
            left, right = 0, 0
        }
    }
    left, right = 0, 0
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == '(' {
            left++
        } else {
            right++
        }
        if left == right {
            maxLength = max(maxLength, 2 * left)
        } else if left > right {
            left, right = 0, 0
        }
    }
    return maxLength
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

复杂度分析

  • 时间复杂度： $O(n)$，其中 $n$ 为字符串长度。我们只要正反遍历两边字符串即可。

  • 空间复杂度： $O(1)$。我们只需要常数空间存放若干变量。

统计信息

通过次数 提交次数 AC比率
206473 577987 35.7%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
有效的括号 简单
字符串 动态规划 栈
上一篇:
31-下一个排列(Next Permutation)
下一篇:
33-搜索旋转排序数组(Search in Rotated Sorted Array)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo