当前位置: 首页 > article >正文

LeetCode 力扣热题100 最长递增子序列

题目解析

最长递增子序列(LIS)

题目描述

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

示例

vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
Solution sol;
int result = sol.lengthOfLIS(nums); // 返回 4

解释:最长递增子序列是 [2, 3, 7, 18],长度为 4。

代码解析

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0; // 处理空输入情况
        
        vector<int> dp(nums.size(), 1); // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
        int ans = 1; // 记录 LIS 长度,最小为 1

        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) { // 如果 nums[i] 能接在 nums[j] 后面
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]); // 维护 LIS 长度
        }
        return ans;
    }
};

详细思路

1. 使用动态规划

定义 dp[i]

• dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度

• 初始化:所有元素至少能单独构成长度 1 的递增子序列,因此 dp[i] = 1。

状态转移方程

如果 nums[i] > nums[j](j < i),则 nums[i] 可以接在 nums[j] 之后:

更新 ans

记录所有 dp[i] 中的最大值。

详细运行步骤

输入:

vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};

1. 初始化

• dp = [1, 1, 1, 1, 1, 1, 1, 1]

• ans = 1

2. 计算 dp[i]

i = 0

• 无 j 满足 j < i,跳过。

i = 1

• j = 0,nums[1] = 9 < 10,跳过。

i = 2

• j = 0, 1,nums[2] = 2 < 10, 9,跳过。

i = 3

• j = 0, 1, 2

• nums[3] = 5 > 2 → dp[3] = max(dp[3], dp[2] + 1) = 2

• dp = [1, 1, 1, 2, 1, 1, 1, 1]

• ans = 2

i = 4

• j = 0, 1, 2

• nums[4] = 3 > 2 → dp[4] = max(dp[4], dp[2] + 1) = 2

• dp = [1, 1, 1, 2, 2, 1, 1, 1]

• ans = 2

i = 5

• j = 0, 1, 2, 3, 4

• nums[5] = 7 > 2, 5, 3 → dp[5] = max(dp[5], dp[3] + 1) = 3

• dp = [1, 1, 1, 2, 2, 3, 1, 1]

• ans = 3

i = 6

• j = 0, 1, 2, 3, 4, 5

• nums[6] = 101 > 2, 5, 3, 7 → dp[6] = max(dp[6], dp[5] + 1) = 4

• dp = [1, 1, 1, 2, 2, 3, 4, 1]

• ans = 4

i = 7

• j = 0, 1, 2, 3, 4, 5, 6

• nums[7] = 18 > 2, 5, 3, 7 → dp[7] = max(dp[7], dp[5] + 1) = 4

• dp = [1, 1, 1, 2, 2, 3, 4, 4]

• ans = 4

最终 dp 状态

[1, 1, 1, 2, 2, 3, 4, 4]

最大值 4,即最长递增子序列长度为 4。

时间复杂度

外层循环 O(n)

内层循环 O(n)

总复杂度 O(n^2)

贪心+二分查找

题目解析

最长递增子序列(LIS)

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

示例

vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
Solution sol;
int result = sol.lengthOfLIS(nums); // 返回 4

解释:最长递增子序列是 [2, 3, 7, 18],长度为 4。

代码解析

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> lis; // 维护 LIS 序列
        for (int num : nums) {
            auto it = lower_bound(lis.begin(), lis.end(), num);
            if (it == lis.end()) {
                lis.push_back(num); // 新增更长的 LIS
            } else {
                *it = num; // 替换以保持最优结构
            }
        }
        return lis.size();
    }
};

思路解析(贪心 + 二分查找)

1. 使用 lis 维护当前的递增子序列

我们不需要真正构造出 LIS 序列,而是用 贪心 + 二分查找 来维护一个数组 lis:

• lis[i] 表示长度为 i+1 的递增子序列的 最小 结尾元素。

• 我们遍历 nums,对每个 num,找到 lis 中 第一个大于等于 num 的位置(使用 lower_bound),然后替换或追加

2. 状态转移

1. 如果 num 大于 lis 的最大元素

• 直接追加 num 到 lis 末尾,增加 LIS 长度。

2. 否则

• 用 lower_bound 找到 lis 中 第一个大于等于 num 的位置替换这样可以保持 lis 的递增性质,并尽可能保持小的元素,给后续的 num 提供更好的递增空间

3. 结果

• lis 的长度即为 LIS 长度(因为 lis 存的是递增子序列的结尾元素)。

lower_bound 解析

作用

auto it = lower_bound(lis.begin(), lis.end(), num);

• lower_bound(begin, end, value) 返回 第一个 >= value 的元素位置。

如果 num 小于 lis 中的某些元素,它会返回可以替换的最小元素的位置

如果 num 大于 lis 里所有元素,返回 lis.end()(表示 num 需要追加到 lis)。

示例

vector<int> lis = {2, 3, 7, 18};
auto it1 = lower_bound(lis.begin(), lis.end(), 5);  // 返回 7 的位置
auto it2 = lower_bound(lis.begin(), lis.end(), 7);  // 返回 7 的位置
auto it3 = lower_bound(lis.begin(), lis.end(), 20); // 返回 lis.end()

详细运行步骤

输入

vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};

初始状态

• lis = {}

遍历 nums

Step 1:num = 10

• lower_bound(lis, 10) → lis 为空,返回 end()。

• 10 追加到 lis:

lis = {10}

Step 2:num = 9

• lower_bound(lis, 9) → 10 位置替换:

lis = {9}

Step 3:num = 2

• lower_bound(lis, 2) → 9 位置替换:

lis = {2}

Step 4:num = 5

• lower_bound(lis, 5) → 大于 2 的第一个位置(插入 5):

lis = {2, 5}

Step 5:num = 3

• lower_bound(lis, 3) → 5 位置替换:

lis = {2, 3}

Step 6:num = 7

• lower_bound(lis, 7) → 大于 3 的第一个位置(插入 7):

lis = {2, 3, 7}

Step 7:num = 101

• lower_bound(lis, 101) → 101 追加到 lis:

lis = {2, 3, 7, 101}

Step 8:num = 18

• lower_bound(lis, 18) → 101 位置替换:

lis = {2, 3, 7, 18}

最终 lis 状态

[2, 3, 7, 18]

长度 4,即 最长递增子序列长度

时间复杂度

每个 num 需要 O(log n) 进行 lower_bound 查找。

最多 n 次操作(遍历 nums)。

总复杂度 O(n log n),比 O(n²) 的 DP 版本更高效。

总结

方法

时间复杂度

适用情况

动态规划 O(n²)

适用于 n ≤ 1000

贪心 + 二分查找 O(n log n)

适用于 n ≤ 10^5

核心思想

• 用 lis 维护递增子序列。

• lower_bound(lis, num) 找到 第一个 >= num 的位置:

若 num 大于 lis 最大值 → 追加到 lis。

否则 → 替换第一个大于等于 num 的元素。

最终 lis.size() 就是 LIS 长度!🚀


http://www.kler.cn/a/584617.html

相关文章:

  • Anaconda conda常用命令:从入门到精通
  • Linux 常用 20 条指令,解决大部分问题
  • 关于vue ui 命令无法无法打开vue项目管理器的记录
  • PHP与数据库连接常见问题及解决办法
  • 四、子串——10. 和为 K 的子数组
  • 动态IP/静态IP
  • 基于单片机的智能电表设计(论文+源码)
  • 【Pandas】pandas Series last_valid_index
  • SQL Server的连接时发生了与网络相关或特定于实例的错误。未找到服务器或无法访问服务器
  • 低代码Web组态开发技术解析
  • 壹佰商城源码搭建-支持打包小程序/公众号/app/h5网页-支持分销-各种营销功能强大
  • SOME/IP-SD -- 协议英文原文讲解8
  • 3.JVM-内部结构
  • 面试基础---支付系统设计深度解析:分布式事务、幂等性与高可用架构
  • 如何在宝塔mysql修改掉3306端口
  • Java中的try-catch在jvm层面是怎么做的?
  • Linux笔记---文件系统硬件部分
  • Selenium 中的 alert 处理
  • MyBatis-Plus 分页查询接口返回值问题剖析
  • C++ 模板初阶总结