LeetCode Medium｜【300. 最长递增子序列】

力扣题目链接
本题有一个简单的解法是动态规划，时间复杂度 O(n^2)，笔者在之前曾做过相关记录：300.最长递增子序列
现在我们来讨论$O(nlog(n))$的解法

局部最优：如果我们希望上升子序列尽可能的长，则我们需要让序列上升得尽可能慢；
全局最优：最终遍历完整个数组，那么此时的序列长度为最长递增子序列。

所以有一个很直观的思路就出来了：

• 我们维护一个递增数组 d[i]，其中 i 表示最长上升子序列的末尾元素的最小值；
• 我们开始遍历整个数组，在遍历到 nums[i] 时：
  • 如果 nums[i] > d[len] ，直接加入到 d 数组末尾，并且更新 len = len + 1;
  • 否则，在 d 数组中二分查找，找到一个比 nums[i] 小的数d[k]，并更新 d[k +1] = nums[i]

这里举一个例子：
对于序列[0, 8, 4, 12, 2]，

• 第一步插入 0，d=[0]；

• 第二步插入 8，d=[0,8]；

• 第三步插入 4，d=[0,4]；

• 第四步插入 12，d=[0,4,12]；

• 第五步插入 2，d=[0,2,12]。

如果你能了解二分查找找到插入位置的话，此题非常简单

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n == 0) {return 0; // 如果数组为空，返回 0}vector<int> d(n + 1, 0); // 用于存储最长递增子序列的数组int len = 1; // 当前 LIS 的长度d[len] = nums[0]; // 初始化第一个元素for (int i = 1; i < n; ++i) {if (nums[i] > d[len]) {// 如果 nums[i] 大于当前 LIS 的最后一个元素d[++len] = nums[i];} else {// 否则，在 d 数组中找到第一个大于或等于 nums[i] 的位置，并替换它int l = 1, r = len, pos = 0;while (l <= r) {int mid = (l + r) / 2;if (d[mid] < nums[i]) {pos = mid; // 找到小于 nums[i] 的最大位置l = mid + 1;} else {r = mid - 1;}}d[pos + 1] = nums[i]; // 替换位置 pos+1 处的值}}return len; // 返回最长递增子序列的长度}
};