• 300. 最长递增子序列

    1. 背

    dp[i]表示有i个字符时最长递增子序列的最小末尾。长度为i的最长递增子序列可能有多个，但是最小末尾只能有一个。例如12378，长度为4的有1237和1238，但是最小的就是7。这么做的目的是为了能让每次更新dp的时候能用更高的效率。传统的dp手段每遍历一次就会遍历一次dp数组，但是用这种最小末尾的可以用二分的方式更新这个dp，因此复杂度就变成了nlogn

    2. 答案

    class Solution {
public:
    int lengthOfLIS(vector& nums) {
        int n = static_cast(nums.size());
        vectordp(n+1,INT_MAX);
        dp[1] = nums[0];
        for(int i=1;i
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    class Solution {
public:
    int lengthOfLIS(vector& nums) { int n = static_cast(nums.size());
        vectordp;
        dp.push_back(nums[0]);
       
        for(int i=1;i
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
  • 相关阅读:
    keycloak~token有效期与session有效期的调研
    python中几个常用小技巧
    Linux 设备模型【1】- devm_kzalloc()
    JAVA笔试面试必备输入输出语句
    设备远程运维的策略与实践
    acwing每日一题（8.12 ~ 8.14）
    Effective objective-c-- 内存管理
    系统设计原则及技术指标
    阿里云服务器包年包月收费模式常见问题汇总（官方资料解答）
    Python：用指定的字拼成这个字本身
  • 原文地址：https://blog.csdn.net/qigezuishuaide/article/details/127712651