news 2026/1/3 13:09:45

最长递增子序列（LIS）：O(n²) DP 与 O(nlogn) 二分优化

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
最长递增子序列（LIS）：O(n²) DP 与 O(nlogn) 二分优化

1. 题目描述：最长递增子序列（LIS）

给定一个整数数组 nums，要求返回其中最长严格递增子序列（Longest Increasing Subsequence, LIS）的长度。leetcode​

  • 严格递增：后一个元素必须大于前一个元素，不能相等。
  • 子序列：从原数组中按顺序选择若干元素，可以不连续，但相对顺序不能变。leetcode​

示例：leetcode​

示例 1：

输入：[10,9,2,5,3,7,101,18] 输出：4 解释：一个 LIS 是 [2,3,7,101]，长度为 4。

示例 2：

输入：[0,1,0,3,2,3] 输出：4

示例 3：

输入：[7,7,7,7,7,7,7] 输出：1。[leetcode](https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150)​

约束：

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4。leetcode​

进阶：能否在 O(n log n) 时间复杂度内求解？leetcode​

2. O(n²) 动态规划：经典解法

2.1 状态定义

用一维数组dp，定义如下：leetcode​

dp[i]：以nums[i]结尾 的最长严格递增子序列的长度。

为什么这样定义？

LIS 一定以某个位置结尾，把“结尾固定在 i”后，就能尝试接在它前面所有比它小的元素后面，做状态转移。leetcode​

2.2 初始化

至少可以选自己一个元素构成长度为 1 的 LIS，所以：leetcode​

对所有i，令dp[i] = 1。

2.3 状态转移

对每个位置i，枚举它前面所有位置j（0 ≤ j < i）：leetcode​

  • 如果nums[i] > nums[j]，则可以把nums[i]接到以j结尾的递增子序列后面：
    dp[i] = max(dp[i], dp[j] + 1)

伪代码：

dp[0..n-1] = 1 for i in [0..n-1]: for j in [0..i-1]: if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) answer = max(dp[0..n-1])

最后答案是dp数组中的最大值，因为 LIS 可以以任意位置结尾。leetcode​

2.4 C 代码实现（O(n²)）

intlengthOfLIS(int*nums,intnumsSize){if(numsSize==0)return0;int*dp=(int*)malloc(sizeof(int)*numsSize);intans=1;// 初始化：每个位置至少为 1for(inti=0;i<numsSize;++i){dp[i]=1;}// 双层循环转移for(inti=0;i<numsSize;++i){for(intj=0;j<i;++j){if(nums[i]>nums[j]){if(dp[j]+1>dp[i]){dp[i]=dp[j]+1;}}}if(dp[i]>ans)ans=dp[i];}free(dp);returnans;}

时间复杂度：外层 n，内层最坏 n，总共 O(n²)；空间复杂度O(n)。leetcode​

3. O(nlogn) 解法：二分 + tail 数组

O(n²) 的瓶颈在于：对每个i都要枚举所有j < i，也就是一个“DP + 枚举前面所有状态”的模式。优化思路是：不再关心每个i的dp值，而是维护“每种长度的 LIS 的最优状态”。leetcode​

3.1 核心思想：维护最小结尾数组 tail

定义一个数组tail：leetcode​

tail[len - 1]：表示长度为len的所有严格递增子序列中，结尾元素最小的那个结尾值。

例如某一时刻：

  • tail[0] = 2：存在长度为 1 的递增子序列，结尾最小可以是 2。
  • tail[1] = 3：存在长度为 2 的递增子序列，结尾最小可以是 3。
  • tail[2] = 7：存在长度为 3 的递增子序列，结尾最小可以是 7。
  • tail[3] = 18：存在长度为 4 的递增子序列，结尾最小可以是 18。leetcode​

这里我们并不关心“具体是哪条序列”，只关心对于每个长度len，最小结尾是多少，因为：

  • 对同样长度len的两个递增子序列，结尾越小越有潜力被接上更多后续元素；
  • 所以同一长度只需要保留“结尾最小”的那一个，其它可以全部丢掉。leetcode​

同时可以证明：tail数组本身是单调递增的（长度越长，结尾最小值越大或相等，但在 LIS 严格递增的场景下，会呈现递增结构）。leetcode​

3.2 对每个 nums[i] 要做什么？

遍历nums，对每一个新元素x = nums[i]做如下操作：leetcode​

  1. 在tail[0..len-1]中用二分查找找到第一个>= x的位置pos。
  2. 如果这样的pos存在：
    • tail[pos]代表某个长度为pos+1的递增子序列的最小结尾；
    • 用x替换它：tail[pos] = x，因为x <= tail[pos]，新的结尾更小，更优。
  3. 如果不存在（即x大于tail中所有元素）：
    • 说明可以在当前最长 LIS 的后面接上x，长度len + 1：
    • tail[len] = x，然后len++。leetcode​

注意这里是 替换，而不是插入：

  • 对某个固定长度k，我们只需要记录“一个最优结尾值”，替换旧值是用更好的状态覆盖掉差的状态；
  • 没必要为同一个长度保留多种结尾值，保留最小那个即可，对后续扩展来说是“支配”的。leetcode​

3.3 示例推导

以nums = [10,9,2,5,3,7,101,18]为例：leetcode​

初始：tail = [], len = 0 x = 10：tail = [10], len = 1 x = 9：第一个 >= 9 是 10，替换 → [9] x = 2：第一个 >= 2 是 9，替换 → [2] x = 5：找 >= 5，不存在（2 < 5），追加 → [2, 5], len = 2 x = 3：第一个 >= 3 是 5，替换 → [2, 3] x = 7：找 >= 7，不存在（2,3 < 7），追加 → [2, 3, 7], len = 3 x = 101：追加 → [2, 3, 7, 101], len = 4 x = 18：第一个 >= 18 是 101，替换 → [2, 3, 7, 18]。[leetcode](https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150)​

最终len = 4，就是 LIS 长度。真实 LIS 可以是[2,3,7,101]或[2,3,7,18]，但题目只要长度即可。leetcode​

3.4 伪代码

tail[0..n-1] // 用来维护每个长度的最小结尾 len = 0 // 当前已知 LIS 的长度 for x in nums: // 在 tail[0..len-1] 中找第一个 >= x 的位置 pos pos = lower_bound(tail, 0, len, x) if pos == len: // x 大于所有结尾，LIS 长度 + 1 tail[len] = x len++ else: // 用更小的结尾值优化长度为 pos+1 的状态 tail[pos] = x answer = len

lower_bound就是“第一个 >= x 的位置”，可以用二分实现，时间 O(log len)，而len <= n。leetcode​

3.5 C 代码实现（O(nlogn)）

intlengthOfLIS(int*nums,intnumsSize){if(numsSize==0)return0;int*tail=(int*)malloc(sizeof(int)*numsSize);intlen=0;// 当前已知的 LIS 长度for(inti=0;i<numsSize;++i){intx=nums[i];// 在 tail[0..len) 中找第一个 >= x 的位置intleft=0,right=len;// 区间是 [left, right)while(left<right){intmid=left+(right-left)/2;if(tail[mid]<x){left=mid+1;}else{right=mid;}}// left 即为 lower_bound 位置tail[left]=x;// 如果 x 放在了当前最长序列的后面，长度 +1if(left==len){len++;}}free(tail);returnlen;}

每个元素做一次 O(log n) 的二分，整体时间复杂度 O(n log n)。
只用了一个长度为 n 的辅助数组tail，空间复杂度 O(n)。leetcode​

4. 两种方法对比总结

维度O(n²) DPO(nlogn) 二分 + tail
核心状态dp[i]：以 i 结尾的 LIS 长度 leetcode​tail[k]：长度为 k+1 的 LIS 的最小结尾 leetcode​
转移方式双层循环枚举 j < i leetcode​对每个 nums[i] 在 tail 中二分找位置 leetcode​
能否恢复序列可以（记录前驱即可）leetcode​只求长度简单，若要恢复需另加结构 leetcode​
时间复杂度O(n²) leetcode​O(nlogn) leetcode​
实现难度思路直观，适合入门 DP leetcode​思想更抽象些，但代码长度不大 leetcode​

如果你想把这篇博客再扩展，可以加一节“如何从 O(n²) 自然想到 O(nlogn)（用‘最优状态’压缩 DP）”，或者加一段“打印 tail 每一步变化”的调试代码，帮助读者直观理解。

https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/1/1 7:19:43

终极文件重命名神器：5步解决批量命名难题

文件重命名是每个电脑用户都会遇到的日常任务&#xff0c;但手动逐个修改既耗时又容易出错。Renamer作为一款基于Node.js开发的命令行工具&#xff0c;通过灵活的插件系统和强大的正则表达式支持&#xff0c;为批量文件重命名提供了完整的解决方案。无论你是开发者、设计师还是…

作者头像 李华
网站建设 2026/1/1 7:19:17

EEGLAB脑电信号处理平台：专业数据分析与可视化全解析

EEGLAB作为神经科学领域备受推崇的开源信号处理环境&#xff0c;为研究者提供了从原始脑电数据到深入洞察的完整解决方案。这个基于MATLAB开发的工具集&#xff0c;凭借其强大的功能模块和灵活的分析流程&#xff0c;已成为脑电数据处理的标准工具之一。 【免费下载链接】eegla…

作者头像 李华
网站建设 2026/1/1 7:19:12

5步掌握Docker容器运行Windows系统的终极指南

5步掌握Docker容器运行Windows系统的终极指南 【免费下载链接】windows Windows inside a Docker container. 项目地址: https://gitcode.com/GitHub_Trending/wi/windows 想要在Linux环境中体验完整的Windows操作系统功能吗&#xff1f;这个开源项目让一切变得简单而高…

作者头像 李华
网站建设 2026/1/2 15:31:53

Steam挂机终极指南：如何安全高效地增加游戏时长

还在为Steam游戏时长不足而烦恼吗&#xff1f;想要轻松收集交易卡却不想整天开着游戏&#xff1f;HourBoostr和SingleBoostr这两款开源神器将彻底改变你的游戏挂机体验&#xff0c;让你在无需安装游戏的情况下安全增加游戏时间。无论你是多账户玩家还是单机用户&#xff0c;都能…

作者头像 李华
网站建设 2026/1/1 7:18:22

AD画PCB操作指南：创建第一个PCB项目

从零开始用Altium Designer画出你的第一块PCB你有没有过这样的经历&#xff1f;脑子里有个酷炫的电子点子&#xff0c;比如做一个会呼吸灯效的智能手环&#xff0c;或者一个能自动浇花的物联网小装置。想法很丰满&#xff0c;可一想到要“画电路板”&#xff0c;顿时就卡住了—…

作者头像 李华
网站建设 2026/1/3 9:34:24

noVNC完整使用指南：浏览器远程桌面控制神器

noVNC完整使用指南&#xff1a;浏览器远程桌面控制神器 【免费下载链接】noVNC VNC client web application 项目地址: https://gitcode.com/gh_mirrors/no/noVNC noVNC是一个功能强大的HTML5 VNC客户端&#xff0c;让你能够通过任何现代Web浏览器直接访问和控制远程桌面…

作者头像 李华