LeetCode 300：最长递增子序列 —— 题解

欢迎阅读 欢迎来到「最长递增子序列」题解之旅本文将带你从“寻找最长的严格递增数字序列”这一经典问题出发深入理解动态规划的核心思想并掌握如何用贪心 二分查找将时间复杂度优化至 O(nlog⁡n)O(nlogn)。在开始之前建议你先了解题目背景这是 LeetCode 300 题给定整数数组nums求最长严格递增子序列LIS的长度。子序列不要求连续但必须保持相对顺序。这是动态规划入门必学的经典题目也是许多复杂 DP 问题的基础。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [10,9,2,5,3,7,101,18]输出4。本文将从问题转化、状态定义、转移方程、初始化、填表顺序到代码实现层层递进同时引入进阶优化贪心 二分让你感受从 O(n2)O(n2) 到 O(nlog⁡n)O(nlogn) 的思维跃迁。即使你对动态规划还不熟悉我们也会从“以每个位置结尾能接多长”这一直觉出发让你轻松抓住核心思想——记住每个长度下最小的末尾值就能贪心地扩展更长的递增序列。现在让我们一起在数组中寻找最长的上升轨迹吧 一、题目300. 最长递增子序列 - 力扣LeetCode二、做题思路1. 问题分析前置分析本题要求返回数组中最长严格递增子序列的长度。经典动态规划解法为 O(n²)但本题进阶要求O(n log n)。核心思路是贪心 二分维护一个数组ret其中ret[i]表示长度为i1的递增子序列的最小末尾元素值。通过让末尾元素尽可能小为后续元素创造更多延长机会从而得到最长长度。2. 贪心策略核心决策规则初始化ret数组将nums[0]放入其中。遍历剩余元素nums[i]若nums[i] ret.back()则直接追加到末尾延长当前最长子序列。否则在ret中二分查找第一个 ≥ nums[i] 的位置并将其替换为nums[i]保持ret严格递增同时减小末尾值为未来更长序列保留潜力。最终ret.size()即为最长递增子序列长度。3. 正确性说明简单版本ret数组记录了各个长度下最小的末尾元素。对于同一个长度末尾值越小后续元素越容易接在后面形成更长的递增子序列。因此每次用新元素替换掉第一个 ≥ 它的位置相当于用更小的值更新该长度下的最优末尾而不会丢失任何潜在的更优解。最终ret的长度就是全局最长递增子序列的长度。4. 实现细节边界防护若数组长度为 0直接返回 0但题目保证 n ≥ 1。使用vectorint ret存储最小末尾值初始为nums[0]。二分查找时left和right分别指向ret的首尾查找第一个≥ nums[i]的位置。注意二分边界条件ret[mid] nums[i]时left mid1否则right mid。5. 返回值目标映射返回ret.size()即最长严格递增子序列的长度。四、代码class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); // 贪心 二分优化 // ret[i] 表示长度为 i1 的递增子序列的“最小末尾元素值”。 // 维护这个数组使其保持严格递增。 vectorint ret; ret.push_back(nums[0]); // 初始时长度为1的末尾就是第一个元素 // 遍历剩余元素 for (int i 1; i n; i) { // 如果当前元素大于 ret 的最后一个元素则可以直接延长最长子序列 if (nums[i] ret.back()) { ret.push_back(nums[i]); } else { // 否则在 ret 中找到第一个 nums[i] 的位置将其替换为 nums[i] // 这样能保证 ret 的单调性并为未来更长的子序列保留更小的末尾值。 int left 0, right ret.size() - 1; while (left right) { int mid (left right) 1; if (ret[mid] nums[i]) { left mid 1; // 中间值小于目标向右收缩 } else { right mid; // 中间值 目标向左收缩 } } // 最终 left right且为第一个 nums[i] 的位置 ret[left] nums[i]; } } // ret 的大小即为最长递增子序列的长度 return ret.size(); } };五、流程图六、正确性说明详细版步骤 1符号与问题建模---------------------------------------------------- | 输入数组 nums长度 n | | 定义 tails 数组tails[i] 表示所有长度为 i1 | | 的递增子序列中最后一个元素的最小值。 | | 例如 nums [7,3,8,4,7,2,14,13] | | 长度1最小末尾2而非7或3 | | 长度2最小末尾4如[3,4]或[2,4] | | 长度3最小末尾7如[3,4,7]或[2,4,7] | | 长度4最小末尾13如[3,4,7,13]或[2,4,7,13] | | 贪心策略维护 tails 数组使其严格递增 | | 且每个位置的值尽可能小。 | ---------------------------------------------------- | v ---------------------------------------------------- | 操作规则遍历 nums对每个元素 x | | ① 若 x tails.back()则直接追加长度1 | | ② 否则在 tails 中二分找到第一个 ≥ x 的位置 | | 将其替换为 x因为更小的末尾值更优。 | ----------------------------------------------------核心思想要得到最长递增子序列只需关心每个长度下最小的末尾元素值。末尾越小越有利于后续扩展。贪心实质每读入一个新元素要么延长当前最长序列若比所有末尾都大要么替换掉某个长度的最小末尾使其变得更小从而为未来创造更多可能。步骤 2关键性质 —— 替换操作的合理性反证与单调性---------------------------------------------------- | 性质 1tails 数组严格递增。 | | 证明若 tails[i] ≥ tails[i1]则长度为 i1 的 | | 子序列末尾更小取其前 i 个元素即可得到长度为 i | | 且末尾 ≤ tails[i1] tails[i] 的子序列矛盾。 | ---------------------------------------------------- | v ---------------------------------------------------- | 性质 2替换操作将第一个 ≥ x 的位置替换为 x | | 保持 tails 的单调性并且不会使任何长度的 | | 最小末尾变大只会变小或不变。 | | 反证若替换后破坏了单调性则与二分查找位置矛盾。| ---------------------------------------------------- | v ---------------------------------------------------- | 性质 3贪心选择当 x tails.back() 时 | | 直接追加是最优的因为此时 x 可以延长所有已有序列| | 得到更长的新序列。否则替换某个位置为更小值 | | 不会减少未来可扩展的长度。 | ----------------------------------------------------详细论证结合反证法单调性假设tails不是严格递增则存在i使得tails[i] tails[i1]。由于tails[i1]是长度为i2的子序列的最小末尾取其前i1个元素构成的长度为i1的子序列其末尾 ≤tails[i1]又因为tails[i1] tails[i]则得到长度为i1的子序列末尾 ≤tails[i]这与tails[i]是长度为i1的最小末尾矛盾。故严格递增成立。替换的合理性当x不大于tails.back()时它不能延长最长序列但可以“优化”某个较短长度的末尾。我们找到第一个tails[pos] x的位置将tails[pos]替换为x。因为x小于等于原值替换后该长度的最小末尾变小或不变且由于pos是第一个满足条件的位置替换后仍保持递增。这个操作不会使任何长度的最小末尾变大因此不会丢失最优解。反证若存在一个最优解其长度更长但贪心算法未能达到该长度则说明在某个步骤中贪心做出了错误替换。但替换操作只是将末尾变小且保持所有长度可选不可能阻断后续扩展。因此贪心选择是安全的。步骤 3归纳证明 —— 扫描完毕 tails 的长度即为答案---------------------------------------------------- | 初始tails 为空处理第一个元素 x追加。 | | 假设处理完前 i 个元素后tails 正确地表示 | | 当前所有长度下的最小末尾值。 | ---------------------------------------------------- | v ---------------------------------------------------- | 处理第 i1 个元素 x | | - 若 x tails.back()则存在长度为 L 的子序列 | | 末尾小于 x故可延长为 L1追加 x 是正确的。 | | - 否则替换第一个 ≥ x 的位置使得该长度的 | | 末尾更小且不改变其他长度归纳假设保持。 | ---------------------------------------------------- | v ---------------------------------------------------- | 最终 tails 的长度 L 即为最长递增子序列的长度。 | | 因为 tails 中的每个位置都对应一个存在的最短末尾 | | 而任何长度大于 L 的递增子序列必然需要一个比 | | tails[L-1] 更大的末尾但扫描完毕所有元素后 | | 不存在这样的元素故 L 是最大值。 | ----------------------------------------------------详细论证归纳假设在扫描完前i个元素后tails数组满足tails[j]是长度为j1的递增子序列的最小末尾值并且数组严格递增。处理新元素x若x tails.back()则当前最长长度L的子序列末尾小于x可以接上x形成长度为L1的子序列因此tails.push_back(x)正确。否则x不能延长最长序列但可以优化某个较短长度。二分查找第一个tails[pos] x替换为x。因为x更小该长度的最小末尾被更新且保持递增。这不会破坏归纳假设。最终循环结束后tails的长度即为扫描过程中能达到的最长递增子序列长度。因为任何更长的子序列其末尾值必须大于等于tails.back()且出现于数组之后但算法遍历完所有元素若存在则会触发追加矛盾。 闭幕 恭喜你完成了「最长递增子序列」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题使用贪心 二分优化核心是维护数组ret其中ret[i]表示长度为i1的递增子序列的最小末尾元素。为什么这样维护能保证得到最长长度如果直接替换某个位置的值会不会“破坏”已经构造的子序列当nums[i]大于ret.back()时直接追加到末尾否则用二分找到第一个大于等于nums[i]的位置并替换。为什么是“大于等于”而不是“大于”如果数组中存在重复元素如[2,2]使用“大于等于”会得到长度1正确若用“大于”则会错误地得到2你能理解其中的区别吗本题也可以用动态规划dp[i]表示以nums[i]结尾的最长递增子序列长度时间复杂度O(n^2)。在n 2500时两者都能通过但当n很大时比如10^5贪心二分的优势就体现出来了。你能说出O(n log n)相比O(n^2)提升在哪里吗ret数组虽然记录的是“最小末尾值”但它并不是真正的子序列。如果题目要求输出具体的最长递增子序列贪心二分还能直接给出吗为什么延伸挑战将题目改为最长非递减子序列允许相等元素递增你只需要修改哪一处比较条件改为动手改改并验证[2,2,2]的结果是否为3。如果要求最长递减子序列只需将nums取反或修改比较符号你能快速写出相应的二分代码吗尝试用动态规划实现本题并对比两种方法在代码复杂度和运行速度上的差异。如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨