LeedCode-300. 最长上升子序列

LeetCode-300. 最长上升子序列

• 方法一：O(n^2)可能会超时；
• 方法二：贪心二分法，使用lower_bound()；

下面是贪心+二分算法：
由于要得到最长的递增子序列，就要让序列中的数增长率尽量小；
需要注意的事项：
1.使用lower_bound()来寻找第一个大于等于当前元素的位置，然后替换值（为什么不用upper_bound(),即寻找第一个大于当前元素的位置，eg：如果当前递增序列为1-3-5-6，当前元素为5，使用upper_bound()会找到值为6的位置并替换，使序列变为1-3-5-5，导致错误）

//包含的头文件
#include <algorithm>int LIS(vector<int>& nums)
{vector<int> dp;for (auto k : nums){//找到第一个大于等于当前元素的dp位置auto ite = lower_bound(dp.begin(), dp.end(), k);//如果没找到，说明当前元素值大于dp序列中所有值，需要加入dp队列的末尾if (ite == dp.end()){dp.emplace_back(k);}else  //找到了大于或则等于的位置，替换为更小的值，始终维护dp队列的值为更小的递增序列；{*ite = k;}}return dp.size();
}

时间复杂度较动态规划大大降低：

如果面试时不能使用lower_bound()和upper_bound(),可以自己手动实现，代码如下：

lower_bound()的实现：
如果没找到则返回末尾元素的下一个，相当于迭代器的end()；

注意事项：

1. while()中的结束条件：left <= right，这样才能保证当没找到合适下标时返回end()，即left+1；
2. 先判断left，过滤掉小于target的元素；
3. 返回值为left；

int My_lower_bound(const vector<int>& nums, int target)
{int left = 0;                  //left左侧的值均<targetint right = nums.size() - 1;   //right右侧的值均>=targetwhile (left <= right){int mid = (right - left) / 2 + left;//首先判断left，这样才能排除掉小于target的下标，如果left==right时还没找到，则返回end();if (nums[mid] < target){left = mid + 1;}else{right = mid - 1;}}return left;
}

upper_bound()的实现：

int My_upper_bound(const vector<int>& nums, int target)
{int left = 0;int right = nums.size() - 1;while (left<=right){int mid = (right - left) / 2 + left;if (nums[mid] <= target){left = mid + 1;}else{right = mid - 1;}}return left;
}