leetcode32-最长有效括号

原题

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

示例 1:

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

示例 2:

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

解法

思想

见代码部分

代码

动态规划解法:

dp[i]代表截至到某个元素的包含有效括号的子串的最长长度(必须包含该字符)。

那么若s.charAt(i) == '(',则dp[i]必为0。若s.charAt(i) == ')',分情况:
+ s.charAt(i-1) == '(',则字符串是...()的形式,此时的dp[i] == dp[i-2]+2
+ s.charAt(i-1) == ')',则字符串是...))的形式,此时要看与s.charAt(i-1)相匹配的左括号的前一个字符是否为(,若是,则dp[i] == dp[i-1]+2+dp[prev-1],若不是,则dp[i] == 0

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

栈的解法需要一些精妙的设计,要保证栈底必须有一个元素(始终留下一个最左边没参与匹配的下标在栈内):

public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max = 0;

        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 {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode32-%e6%9c%80%e9%95%bf%e6%9c%89%e6%95%88%e6%8b%ac%e5%8f%b7/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月12日
下一篇 2020年6月13日

相关推荐

  • leetcode131-分割回文串

    原题 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], …

    算法 2020年5月22日
    0100
  • leetcode559-N叉树的最大深度

    原题 给定一个 N 叉树,找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如,给定一个 3叉树 : 我们应返回其最大深度,3。 说明: 树的深度不会…

    2020年1月20日
    060
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0400
  • leetcode5-最长回文子串

    原题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有…

    算法 2020年2月20日
    0110
  • leetcode17-电话号码的字母组合

    原题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入: "23" 输出: …

    2020年5月3日
    0130
  • leetcode429-N叉树的层序遍历

    原题 给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:…

    2020年1月20日
    0140
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode189-旋转数组

    原题 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4…

    算法 2019年11月22日
    050
  • 剑指offer59-队列的最大值

    原题(来源Leetcode) 请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的时间复杂度…

    算法 2020年3月7日
    0130
  • leetcode392-判断子序列

    原题 https://leetcode.cn/problems/is-subsequence/description 解法 最简单的双指针略。 对于进阶场景:如果有大量输入的 S,…

    算法 2024年3月24日
    040

发表回复

登录后才能评论