力扣300:最长递增子序列(Java动态规划+双指针)

这篇具有很好参考价值的文章主要介绍了力扣300:最长递增子序列(Java动态规划+双指针)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目描述

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 
示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。


示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4


示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1
 

提示:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104
 

进阶:

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

二、思路讲解

        用dp[i] 表示以i 结尾的序列中,最大递增子序列的长度。那么我们在每个i 处,往前找比自己小的数字(记为j 处),将该处的dp值+1,即是i处的dp值(说明i处的数字可以接在j 处后面组成递增子序列)。dp数组中的最大值即为所求。

三、Java代码实现

class Solution {
    public int lengthOfLIS(int[] nums) {

        //数组长度
        int len = nums.length;
        //最后结果
        int res = 0;
        //dp[i]表示以i结尾的序列的最大递增子序列长度
        int []dp = new int[len];
        //给dp赋初值
        for(int i=0; i<len; i++) {
            dp[i] = 1;
        }

        for(int i=0; i<len; i++) {
            int big = 0;
            for(int j=0; j<i; j++) {
                if(nums[j]<nums[i]) {
                    big = Math.max(big, dp[j]);
                }
            }
            dp[i] = big + 1;
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

        时间复杂度:        O(N^2)

        空间复杂度:        O(N) 

四、算法优化

        进阶要求是要时间复杂度为nlogn。我们的算法的时间复杂度主要为:遍历nums数组,使用n,无法优化;线性遍历[0, i-1) 求dp[i],使用n。我们可以考虑重新设计dp的思路。

        设计一个tail数组,tail[i] 表示长度为i的递增序列的最小末尾数字。例如,4 5 1 9 8 5 序列中,长度为1的递增序列有4,5,1,9,8,5,所以tail[1]为1;长度为1的递增序列有4 5,4 9,4 8,

5 8, 5 9……所以tail[2] 为5;长度为3的递增序列有 4 5 9,4 5 8,所以tail[3] 为8。可以看出,tail为一个递增序列,在查找操作时,我们可以使用二分查找。

        那么,我们在计算tail[i]的时候,只需要遍历nums,找到第一个比num大的tail[k],说明num更适合放在tail[k-1]位置,而不能接在tail[k]位置(接上就不递增了)。如果num比tail中所有数字都大,那就说明num适合接在所有递增序列之后,这时递增序列的长度又可以增加了。

        参考:力扣300. 最长递增子序列(动态规划 + 二分查找,清晰图解)

class Solution {
    public int lengthOfLIS(int[] nums) {

        //数组长度
        int len = nums.length;
        //tail[i]表示,长度为i的递增序列的最小末尾数字
        int []tail = new int[len];

        //题目所求 递增序列的最大长度
        int resLen = 0;
        for(int i=0; i<len; i++) {
            int left = 0;
            int right = resLen;
            //二分查找 找到比nums[i]大的tail,若找不到,说明nums[i]适合放在所有序列的末尾,那么就向后更新一个长度
            while(left < right) {
                int mid = (left+right) / 2;
                if(tail[mid]<nums[i]) {
                    left = mid+1;
                } else {
                    right = mid;
                }
            }
            tail[left] = nums[i];
            //更新长度
            resLen = resLen==right? (resLen+1) : resLen;
        }
        return resLen;
    }
}

        时间复杂度:        O(NlogN)

        空间复杂度:        O(N)文章来源地址https://www.toymoban.com/news/detail-660819.html

到了这里,关于力扣300:最长递增子序列(Java动态规划+双指针)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣300. 最长递增子序列

    思路: 假设 dp[i] 为前 i 个元素构成的最长递增子序列的个数,包含 nums[i]; 则 dp[i] 构成序列上一个元素 nums[j] 构成最长递增子序列 dp[j],则 dp[i] = dp[j] + 1; 如果动态取 j ∈ [0, i - 1],则选取其中最长递增子序列值中最大的,其值 + 1 来更新 dp[i] 的值;

    2024年02月04日
    浏览(41)
  • 最长递增子序列——力扣300

    2024年02月12日
    浏览(34)
  • 动态规划之最长递增子序列

    leetcode 300 最长递增子序列 1.定义dp数组:dp[i]表示以nums[i]结尾的最长递增子序列的长度。 2.定义递推公式 dp[i] = max(dp[j] + 1, dp[i]) 因为dp[j] + 1中的dp[j]并非是在前一个已经加1的dp[j]的基础之上再加上1。若从初始状态加1,而dp[i]永远保持的是最大的状态,则dp[j] + 1肯定要小一些。

    2024年01月23日
    浏览(45)
  • 动态规划算法 | 最长递增子序列

    通过查阅相关资料 发现动态规划问题一般就是求解最值问题 。这种方法在解决一些问题时应用比较多,比如求最长递增子序列等。 有部分人认为动态规划的核心就是:穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值。 首先,笔者认为动态规划中

    2024年02月06日
    浏览(54)
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(56)
  • 【动态规划】求最长递增子序列问题

    最长递增子序列(Longest Increasing Subsequence, LIS ) 子序列:对于任意序列s,它的子序列是通过删除其中零个或多个元素得到的另⼀个序列 注:剩余元素的相对顺序保持不变 给定n个整数组成的序列 s [ 1... n ] s[1...n] s [ 1... n ] ,求最长递增子序列LIS(的长度) 8 3 6 1 3 5 4 7 假设

    2024年02月03日
    浏览(49)
  • 动态规划9:最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列、不相交的线、最长子序和

    例题300: 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 确定dp数组和下标含义 dp[i]表示在第i个元素的最长子序列数

    2024年04月08日
    浏览(44)
  • 【学会动态规划】最长递增子序列的个数(28)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 这道题的题目非常好理解,就是求出最长

    2024年02月11日
    浏览(40)
  • 【LeetCode: 673. 最长递增子序列的个数 | 动态规划】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月03日
    浏览(64)
  • Leetcode:300. 最长递增子序列、674. 最长连续递增序列(C++)

    目录 300. 最长递增子序列 题目描述: 实现代码: 原理思路: 674. 最长连续递增序列 题目描述: 实现代码: 原理思路: 题目描述:         给你一个整数数组  nums  ,找到其中最长严格递增子序列的长度。 子序列  是由数组派生而来的序列,删除(或不删除)数组中

    2024年02月11日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包