贪心算法学习——最长单调递增子序列

编辑

一，题目

二，题目接口

三，解题思路和代码

一，题目

给你一个整数数组 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

二，题目接口

class Solution {
public:int lengthOfLIS(vector<int>& nums) {}
};

三，解题思路和代码

这道单调递增子序列的算法题的解法有很多，比如动态规划，记忆化搜索等等。但是使用动态规划和记忆化搜索的时间复杂度都比较高大概都是O(n^2)。但是使用贪心算法的思想来解答这道题的话能让时间复杂度下降到O(n*log2N)。现在就来说一下该如何实现这个算法。

步骤：

1，首先我们得要创建一个vector<int>类型的数组ret。这个数组是用来存储子序列的。

2，对nums数组进行遍历对于每个数组元素nums[i]会有两种不同的情况：

1.大于ret.back(),这个时候直接将这个nums[i]插入到ret的最后面。

2.小于ret.back(),这个时候便要采用二分查找法在ret中找到一个合适的位置放入 nums[i].

3.遍历结束后便可以返回ret.size()。

代码如下：
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int>ret;ret.push_back(nums[0]);for(int i = 1;i<nums.size();i++){if(nums[i]>ret.back()){ret.push_back(nums[i]);}else{int left = 0;int right = ret.size()-1;while(left<right){int mid = (right+left)/2;if(nums[i]>ret[mid]){left = mid+1;}else{right = mid;}}ret[right] = nums[i];}}return ret.size();}
};