57 最长递增子序列

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


给你一个整数数组 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
  • − 1 0 4 -10^4 104 <= nums[i] <= 1 0 4 10^4 104

进阶:

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

题解1 DP O ( n 2 ) O(n^{2}) O(n2)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int maxN = INT_MIN;
        /**
        dp[i] : i处数值对应的最长子序列长度
        **/
        for(int i = 1; i < nums.size(); i++){    
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j]+1);
            }
            maxN = max(maxN, dp[i]);
        }
        return maxN == INT_MIN ? 1 : maxN;
    }
};

57 最长递增子序列,HOT100,DP,贪心,算法,leetcode,数据结构

题解2 贪心+二分搜索(ref. from Leetcode) O ( n l o g ( n ) ) O(n log(n)) O(nlog(n))

“从左到右(序列顺序),维护一个每个元素尽可能小的LIS备选集合S”

每个元素尽可能小,这样更可能在末尾加上一个新的值,构成一个更大的LIS

只增加(add)和替换(swap),因此完成遍历后S的长度一定等于LIS的长度,部分元素可能被你替换掉了,所以在整个遍历过程中,这个集合S可能并不是LIS本身,尽管如此,LIS的元素一定曾出现在S中(但可能在遍历过程中被swap覆盖掉了)

鼓掌!!这个思想好棒

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(1 == nums.size()) return 1;
        // p[i]: 长度为i的最长上升子序列的末尾元素最小值
        vector<int> p(nums.size()+1, 0);
        int len = 1;
        p[len] = nums[0];
        
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] > p[len]){
                len ++;
                p[len] = nums[i];
            }else{
                // 在i位置不用遍历得到dp值
                // 长度=len+1的子序列的最小值 > nums[i],为了保持p的递增,需要修改某个位置的值
                // 用二分找到最近的j, 满足p[j] < nums[i] < p[j+1]
                // s.t. p[j+1] = nums[i];
                // 如果找不到, 说明所有的数都比 nums[i] 大,此时要更新 d[1],所以这里将 pos 设为 0
                int left = 1;
                int right = len;
                int pos = 0;
                // 最希望的是改p[len], 所以判断条件 有 =
                // 实际上是想不用遍历,用二分检查一遍 nums[i]是不是大于len+1情况里的倒数第二个最大的数吧
                while(left <= right){
                    int mid = (left+right) >> 1;
                    // 找到了j
                    if(nums[i] > p[mid]){
                        pos = mid;
                        left = mid+1;
                    }  
                    else{
                        right = mid-1;
                    }
                }
                p[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

57 最长递增子序列,HOT100,DP,贪心,算法,leetcode,数据结构文章来源地址https://www.toymoban.com/news/detail-724336.html

到了这里,关于57 最长递增子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【重点】【DP】300. 最长递增子序列

    题目 更好的方法是耐心排序,参见《算法小抄》的内容!!! 基础解法必须掌握!!!

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

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

    2024年02月11日
    浏览(57)
  • 【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)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(48)
  • leetcode300. 最长递增子序列 子序列(不连续)

    https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 LIS即最长上升子序列,指

    2024年02月14日
    浏览(43)
  • 算法刷题Day 52 最长递增子序列+最长连续递增子序列+最长重复子数组

    我自己想出来的方法,时间复杂度应该是 O(n2) 滑动窗口 连续的话,可以考虑用滑动窗口 动态规划 贪心算法

    2024年02月14日
    浏览(54)
  • leetcode300. 最长递增子序列(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/longest-increasing-subsequence 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序

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

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

    2024年02月03日
    浏览(64)
  • ( 动态规划) 674. 最长连续递增序列 / 718. 最长重复子数组——【Leetcode每日一题】

    难度:简单 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l r) 确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月05日
    浏览(52)
  • 动态规划算法 | 最长递增子序列

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

    2024年02月06日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包