题目
给你一个整数数组 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 。示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
解答
- n2复杂度动态规划
解题思路：
- dp[i]:以nums[i]为结尾的最长递增子序列的长度
- 递推公式：max(dp[i],dp[j]+1),
- dp[i]至少为1（初始化条件）
- 遍历顺序：i从小到大 j从大到小，从小到大都可以（0到i之间的每一个元素）
- 最终返回dp数组中的最大值
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1); // 初始化dp数组，每个元素默认长度为1
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1); // dp数组的更新
}
}
}
return *max_element(dp.begin(), dp.end());
}
};- n log(n)复杂度贪心
交换状态与状态值
令g[i]表示长度为i+1的IS的末尾元素的最小值
g是严格递增的。
推论1:一次只能更新一个位置，单调递增序列不能有相同元素。
推论2:更新的位置是第一个大于等于nums[i]的数的下标。
算法：在g上用二分查找快速找到第一个大于等于nums[i]的下标j。如果j不存在，那么nums[i]直接加到g末尾;否则修改g[j]为nums[i].
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> tails; // 用于存储递增子序列的末尾元素
for (int num : nums) {
// lower_bound 返回一个迭代器，指向容器中第一个大于等于给定值的元素。
auto it = lower_bound(tails.begin(), tails.end(), num); // 在 tails 中寻找第一个大于等于 num 的元素
if (it == tails.end()) {
tails.push_back(num); // 如果找不到，则将 num 添加到末尾
} else {
*it = num; // 否则，更新找到的元素，因为它可以作为更长递增子序列的末尾元素
}
}
return tails.size(); // 返回 tails 数组的长度，即为结果
}
};