题目描述
LeetCode 300 — 最长递增子序列 (Medium)
给定一个整数数组 nums，找到其中最长严格递增子序列的长度。
示例 1：
- 输入：
nums = [10,9,2,5,3,7,101,18] - 输出：
4 - 解释：最长递增子序列是
[2,3,7,101]，长度为 4。
示例 2：
- 输入：
nums = [0,1,0,3,2,3] - 输出：
4
示例 3：
- 输入：
nums = [7,7,7,7,7,7,7] - 输出：
1
约束：
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
求解思路
暴力枚举所有子序列再逐一判断是否递增，时间复杂度是指数级的，显然不可行。最朴素的动态规划思路是：设 dp[i] 为以 nums[i] 结尾的最长递增子序列长度，对每个位置遍历它前面的所有元素来更新状态，总复杂度 O(n²)。这个方法能过，但题目进阶要求 O(n log n)，需要换个角度思考。
关键在于换一种 dp 的定义方式。不以「以某个元素结尾」来定义状态，而是设 dp[i] 为长度为 i + 1 的递增子序列中，所有可能结尾元素的最小值。这个数组天然单调递增——如果长度为 3 的递增子序列最小结尾是 5，那长度为 4 的递增子序列结尾一定大于 5，否则它截取前 3 个元素就能得到一个结尾更小的长度 3 子序列，与最小值矛盾。
有了单调性，就能用二分查找加速维护。遍历每个元素 num 时：如果 num 大于 dp 末尾，说明它可以接在当前最长子序列后面，直接追加；否则，用二分查找在 dp 中找到第一个大于或等于 num 的位置，用 num 替换它。替换操作的含义是：对于该长度的子序列，找到了一个更小的结尾元素，为后续构造更长的子序列留出更多空间。
最终 dp 数组的长度就是最长递增子序列的长度。注意 dp 中存的并不是一个真实的子序列，它只是维护了各长度下的最优结尾信息。
解法：二分查找
/*
设 dp[i] 代表长度为 i + 1 的递增子序列中，所有可能结尾元素的最小值。
dp 天然单调递增
如果 num 比 dp 数组中所有元素都大，直接把它追加到 dp 的末尾。
否则，用二分查找在 dp 中找到第一个大于或等于 num 的元素，并用 num 替换它。
*/
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp;
dp.push_back(nums[0]);
for(int i = 1; i < n; i++){
if(nums[i] > dp.back()){
dp.push_back(nums[i]);
}else{
int left = 0;
int right = dp.size() - 1;
while(left < right){
int mid = left + (right - left) / 2;
if(nums[i] <= dp[mid]){
right = mid;
} else{
left = mid + 1;
}
}
dp[left] = nums[i];
}
}
return dp.size();
}
};
复杂度： 时间 O(n log n)，外层遍历数组 O(n)，内层二分查找 O(log n)；空间 O(n)，dp 数组最坏情况下与原数组等长。