题目
给你一个整数数组 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
分析
为了求解最长严格递增子序列（LIS）的长度，我们可以使用贪心算法结合二分查找，将时间复杂度优化，这是目前解决该问题的最优解法之一。
贪心+二分查找
贪心策略：维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的严格递增子序列的最小末尾元素。通过不断更新这个数组，最终数组的长度即为最长严格递增子序列的长度。
二分查找：对于当前遍历到的元素 num，在 tails 中找到第一个大于等于 num 的位置，并用 num 替换该位置的元素。若 num 大于 tails 中的所有元素，则直接将其添加到 tails 末尾。
时间复杂度：O()，
是数组的长度
空间复杂度：O()
#include <vector>
#include <algorithm>
class Solution {
public:
int lengthOfLIS(std::vector<int>& nums) {
std::vector<int> tails;
for (int num : nums) {
// 在 tails 中查找第一个大于等于 num 的位置
auto it = std::lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
// num 比所有元素都大，添加到末尾
tails.push_back(num);
} else {
// 替换第一个大于等于 num 的元素为 num
*it = num;
}
}
return tails.size();
}
};知识充电
lower_bound 函数
在 C++ 中，lower_bound 是 <algorithm> 头文件中提供的一个算法，用于在 有序序列 中查找满足特定条件的元素位置。它的核心功能是找到第一个 不小于（即大于或等于）给定值的元素的位置。
lower_bound 本质是二分查找的一种实现，时间复杂度为 O(log n)，常用于高效查找有序序列中的位置。
定义
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);- 参数：
first和last：指定查找的区间（左闭右开，即[first, last)）。value：要查找的值。comp（可选）：自定义比较函数，用于定义 “小于” 的规则（默认为<）。
- 返回值：指向第一个 不小于
value的元素的迭代器。如果所有元素都小于value，则返回last。