当前位置：首页 > news >正文

【Hot 100 刷题计划】 LeetCode 300. 最长递增子序列 | C++ 动态规划贪心二分

news 2026/4/15 0:27:14

LeetCode 300. 最长递增子序列

📌 题目描述

题目级别：中等

给你一个整数数组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。

💡 解法一：动态规划 (回头找垫脚石)

面对子序列问题，动态规划是最正统的解法。

状态定义：
定义dp[i]表示：以nums[i]这个数结尾的最长递增子序列的长度。
(注意：这里必须是以它结尾，这样我们才能确切知道下一个数能不能接在它后面。)

状态转移方程：
假设我们正在考察第i个数字，我们如何求它的dp[i]？
我们只需要回头看它前面的所有数字（假设索引为j，0 <= j < i）：
只要nums[i] > nums[j]，说明nums[i]可以完美地接在nums[j]的后面，形成一个更长的递增子序列。
所以我们在所有符合条件的j中，挑一个dp[j]最大的接上去，再加上自己本身的长度 1 即可：

dp[i] = max(dp[i], dp[j] + 1)

初始化：
每个数字自己本身就可以构成一个长度为 1 的子序列，所以dp数组初始全部赋值为1。

💻 C++ 代码实现 (DP 法)

classSolution{public:intlengthOfLIS(vector<int>&nums){intn=nums.size();if(n==0)return0;// 规范写法：使用 vector 开辟状态数组，并全部初始化为 1vector<int>dp(n,1);intres=1;for(inti=0;i<n;i++){// 内层循环：回头寻找可以接上去的“垫脚石”for(intj=0;j<i;j++){if(nums[i]>nums[j]){dp[i]=max(dp[i],dp[j]+1);}}// 记录整个过程中出现的最大长度res=max(res,dp[i]);}returnres;}};

进阶挑战：你能将算法的时间复杂度降低到O(nlog⁡n)O(n \log n)O(nlogn)吗?

💡 解法二：贪心策略 + 二分查找

为了让递增子序列尽可能的“长”，我们需要秉持一个贪心的原则：让子序列的增长速度尽可能的慢！
换句话说，每次加进来的数字越小，后面能接上的数字就越多。

我们可以维护一个名为tails的数组：

tails[k]表示：长度为k+1的递增子序列中，末尾最小的那个数字。

核心运作机制：
遍历原数组nums，对于当前数字num：

如果num比tails数组的最后一个元素还要大：
简直完美！说明它可以直接接在当前最长的子序列后面，让最大长度加 1。我们直接把它push_back到tails末尾。
如果num没有比最后一个元素大：
它虽然不能增加最长子序列的长度，但它是一个“潜力股”。我们要在tails数组中找到第一个大于等于num的元素，并用num去替换它！
为什么？因为tails数组天然是严格递增的！把较大的末尾元素换成较小的num，不会改变当前子序列的长度，但会让末尾数字变小，为后续接上更多的数字创造了有利条件。

由于tails数组是严格递增的，在其中寻找“第一个大于等于num的元素”这一步，我们可以直接使用二分查找，将这部分的时间从O(N)O(N)O(N)降到O(log⁡N)O(\log N)O(logN)。

💻 C++ 代码实现 (贪心+二分法)

classSolution{public:intlengthOfLIS(vector<int>&nums){// tails 数组存储当前各个长度的递增子序列的最小末尾元素vector<int>tails;for(intnum:nums){// 如果 tails 为空，或者当前数字大于 tails 的最后一个数字，直接追加if(tails.empty()||num>tails.back()){tails.push_back(num);}else{// 否则，使用二分查找找到 tails 中第一个 >= num 的元素intl=0,r=tails.size()-1;while(l<r){intmid=l+(r-l)/2;if(tails[mid]>=num){r=mid;// 目标在左侧或就是 mid}else{l=mid+1;// 目标在右侧}}// 用更小的 num 替换掉原来的较大元素，培养潜力tails[l]=num;// 也可以一行代码搞定：// *lower_bound(tails.begin(), tails.end(), num) = num;}}// tails 数组的最终长度，就是最长递增子序列的长度returntails.size();}};