目錄

?編輯

一，題目

二，題目接口

三，解題思路和代碼

---

一，題目

給你一個整數(shù)數(shù)組?nums?，找到其中最長嚴格遞增子序列的長度。

子序列?是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7]?是數(shù)組?[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) {}
};

三，解題思路和代碼

? ? ? 這道單調遞增子序列的算法題的解法有很多，比如動態(tài)規(guī)劃，記憶化搜索等等。但是使用動態(tài)規(guī)劃和記憶化搜索的時間復雜度都比較高大概都是O(n^2)。但是使用貪心算法的思想來解答這道題的話能讓時間復雜度下降到O(n*log2N)?，F(xiàn)在就來說一下該如何實現(xiàn)這個算法。

? ? ?步驟：

? ?1，首先我們得要創(chuàng)建一個vector<int>類型的數(shù)組ret。這個數(shù)組是用來存儲子序列的。

? ?2，對nums數(shù)組進行遍歷對于每個數(shù)組元素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();}
};