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日

相关推荐

  • 剑指offer17-打印从1到最大的n位数

    原题(来源Leetcode) 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: …

    算法 2020年4月17日
    080
  • leetcode153-寻找旋转排序数组中的最小值

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月3日
    080
  • 力扣杯春季个人赛-剧情触发时间

    这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?,虽然大家的通过率也不咋地。。 最后排名 我记录一道做出来的题吧,这道题是一道中等题,通过率如下,虽然题目不难,但由于时…

    2020年4月18日
    0410
  • leetcode14-最长公共前缀

    原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “…

    算法 2019年11月18日
    090
  • 剑指offer44-数字序列中某一位的数字

    原题(来源Leetcode) 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位…

    算法 2020年6月15日
    02870
  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0130
  • 数组元素左右两边最近较小元素

    原题(来源牛客网) 给定一个不含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。 实例: 输入: ar…

    算法 2020年4月26日
    0690
  • leetcode328-奇偶链表

    原题 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空…

    算法 2019年12月16日
    0130
  • 海量数据-两种方法解决top k问题

    假如提供一百万个数据(甚至更大)的无序数组,如何从中获取最大的k个元素? 最容易想到的是先降序排序然后获取前k个元素,那假设我们用最常用的O(nlogn)级别的排序算法,要获取to…

    2020年4月4日
    0200
  • leetcode235-二叉搜索树的最近公共祖先

    原题 给定一个二叉二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x …

    2020年1月17日
    0100

发表回复

登录后才能评论