每日计划-1206

1. 完成 300. 最长上升子序列

有两种办法，一是使用状态规划，二是用二分法，递推。利用桶排序思想，出自最长递增子序列（nlogn 二分法、DAG 模型和延伸问题） | 春水煎茶

代码实现：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {// 定义二维向量buckets，用于存放不同长度的递增子序列（每个内层向量代表一个递增子序列）// 这里先将第一个元素nums[0]作为长度为1的递增子序列放入buckets中vector<vector<int>> buckets;buckets.push_back({nums[0]});// 从数组的第二个元素（索引为1）开始遍历整个数组for (int i = 1; i < nums.size(); ++i) {// 使用lower_bound函数在buckets中查找当前元素nums[i]合适的插入位置// 这里自定义了比较函数，比较逻辑是根据每个内层向量的最后一个元素大小来判断// 目的是找到第一个满足条件的位置，使得当前元素nums[i]能维持buckets中各子序列结尾元素的递增特性auto it = lower_bound(buckets.begin(), buckets.end(), vector<int>{nums[i]},[](const vector<int>& a, const vector<int>& b) {return a.back() < b.back();});// 如果找到的位置是buckets的末尾，意味着当前元素nums[i]比所有已有的子序列结尾元素都大// 那么就可以将nums[i]作为一个新的、更长的递增子序列的开头元素，新建一个内层向量放入buckets中if (it == buckets.end()) {buckets.push_back({nums[i]});} // 如果找到的位置不是末尾，说明当前元素nums[i]可以加入到已有的某个子序列中（以更新该子序列）// 这里直接将nums[i]添加到对应的子序列（即对应的内层向量）中，使得这个子序列结尾元素更新为nums[i]// 并且依然能保证该子序列是递增的，同时也有助于后续可能出现更长的子序列拓展情况else {it->push_back(nums[i]);}}// 最后buckets中存放了不同长度的递增子序列，其大小就代表了最长递增子序列的长度（即有多少种不同长度的子序列）return buckets.size();}
};