32. 最长有效括号

今天药忘吃喽~ 2022-09-10 11:27 156阅读 0赞

[https://leetcode-cn.com/problems/longest-valid-parentheses/][https_leetcode-cn.com_problems_longest-valid-parentheses]

难度困难1451收藏分享切换为英文接收动态反馈

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

**示例 1：**

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

**示例 2：**

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

**示例 3：**

输入：s = ""
    输出：0

**提示：**

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

通过次数184,743提交次数518,763

class Solution {
        public int longestValidParentheses(String s) {
            int max= 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;
                    }
                    max = Math.max(max, dp[i]);
                }
            }
            return max;
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_longest-valid-parentheses]: https://leetcode-cn.com/problems/longest-valid-parentheses/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/329e31a90c054e53bd44c193d00cf7d4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关【力扣刷题】32. 最长有效括号

目录题目：方法一：解题思路：代码：方法二：解题思路：代码：题目：给你一个只包含 `'('` 和 `')'` 的字符串，找出最长有效（格式

灰太狼/ 2023年09月28日 13:06/ 0 赞/ 7 阅读

相关 leetcode 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

Dear 丶/ 2023年08月17日 15:43/ 0 赞/ 119 阅读

相关 leetcode 32. 最长有效括号

思路：动态规划，dp\[i\]表示以s\[i\]结尾的，最长的子串长度很明显,当s\[i\]=='('时，不能构成完整子串，dp\[i\]=0, 当s\[i\]==

桃扇骨/ 2023年07月02日 10:27/ 0 赞/ 7 阅读

相关 leetcode32 最长有效括号

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

た入场券/ 2023年06月18日 05:54/ 0 赞/ 15 阅读

相关 32. 最长有效括号

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号

我会带着你远行/ 2023年02月22日 13:55/ 0 赞/ 10 阅读

相关 Leetcode 最长有效括号

利用括号匹配的算法以及栈，就可以算出匹配序列，然后利用两个变量记录有效括号的起始值与结束值，就可以得到最长有效括号。 include<stdio.h> inc

左手的ㄟ右手/ 2023年02月22日 13:52/ 0 赞/ 8 阅读

相关最长有效括号

最长有效括号 1、参考资料 https://leetcode-cn.com/problems/longest-valid-parentheses/ 2、题目要求

今天药忘吃喽~/ 2022年12月05日 10:00/ 0 赞/ 162 阅读

相关 32. 最长有效括号

[https://leetcode-cn.com/problems/longest-valid-parentheses/][https_leetcode-cn.com_prob

今天药忘吃喽~/ 2022年09月10日 11:27/ 0 赞/ 157 阅读

相关 LeetCode32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。示例 1：输入：s = "(()" 输出：2 解释：最长有效括号子串

系统管理员/ 2022年09月08日 00:12/ 0 赞/ 143 阅读

相关 LeetCode 32. Longest Valid Parentheses (最长有效括号)

题目描述：给定一个只包含 `'('` 和 `')'` 的字符串，找出最长的包含有效括号的子串的长度。示例：输入: "(()" 输出: 2 解

╰+哭是因爲堅強的太久メ/ 2022年05月11日 04:04/ 0 赞/ 163 阅读