leetcode32最长有效括号hard最特殊一种解法

喜欢ヅ旅行 2023-07-05 08:00 5阅读 0赞

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

示例 1:

输入: “(()”  
输出: 2  
解释: 最长有效括号子串为 “()”  
示例 2:

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

思路： 原本这是一道应该用动态规划解的，但是出现了一种神奇的解法，特此记录一下。

class Solution {
        
        public int longestValidParentheses(String s) {
        
            int l = 0;
            int r = 0;
            int ans = 0;
            for (int i = 0;i < s.length();i++) {
        
                if (s.charAt(i) == '(') {
        
                    l++;
                } else {
        
                    r++;
                }
                if (l == r) {
        
                    ans = Math.max(ans,l*2);
                } else if (l <= r) {
        
                    l = r = 0;
                }
            }
    
            l = r = 0;
            // 右到左
            for (int j = s.length()-1;j >= 0;j--) {
        
                if (s.charAt(j) == '(') {
        
                    l++;
                } else {
        
                    r++;
                }
                if (l == r) {
        
                    ans = Math.max(ans,l*2);
                } else if (r <= l){
        
                    l = r = 0;
                }
            }
    
            return ans;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 最长有效括号

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

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

相关 leetcode32最长有效括号hard最特殊一种解法

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

喜欢ヅ旅行/ 2023年07月05日 08:00/ 0 赞/ 6 阅读

相关 leetcode 32. 最长有效括号

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

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

相关 leetcode力扣（32）----------最长有效括号

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

阳光穿透心脏的1/2处/ 2023年06月25日 06:22/ 0 赞/ 15 阅读

相关 leetcode32 最长有效括号

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

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

相关 32. 最长有效括号

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

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

相关 Leetcode 最长有效括号

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

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

相关 32. 最长有效括号

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

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

相关 LeetCode32. 最长有效括号

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

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

相关【leetcode】最长有效括号 O(n)的两种解法

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVp

た入场券/ 2022年03月20日 02:40/ 0 赞/ 129 阅读