300. 最长递增子序列——【Leetcode每日刷题】

向右看齐 2024-03-26 20:15 73阅读 0赞

### 300. 最长递增子序列 ###

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

##### 提示： #####

*   1 < = n u m s . l e n g t h < = 2500 1 <= nums.length <= 2500 1<=nums.length<=2500
 *   − 1 0 4 < = n u m s \[ i \] < = 1 0 4 -10^4 <= nums\[i\] <= 10^4 −104<=nums\[i\]<=104

##### 进阶： #####

*  你能将算法的时间复杂度降低到 O(n log(n)) 吗?

#### 思路： ####

##### 法一：动态规划 #####

本题动态规划的关键就是 dp\[i\] ，表示 **最后一位是 nums\[i\]** 的最长上升子序列的长度。（注意： nums\[i\]必须被选取！）

**动规五部曲：**

1.  dp\[i\]的定义

dp\[i\] 表示 i 之前包括 i 的最长上升子序列的长度。

1.  状态转移方程

位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。

所以：if (nums\[j\] < nums\[i\]) dp\[i\] = max(dp\[i\], dp\[j\] + 1);

注意这里不是要 dp\[i\] 与 dp\[j\] + 1进行比较，而是我们要取 dp\[j\] + 1的最大值。

1.  dp\[i\]的初始化

每一个 i，对应的 dp\[i\]（即最长上升子序列）起始大小至少都是是1.

1.  确定遍历顺序

dp\[i\] 是有 0 到 i-1各个位置的最长升序子序列 推导而来，那么遍历 i 一定是从前向后遍历。j 其实就是0到 i-1，遍历i的循环里外层，遍历 j 则在内层。

1.  举例推导dp数组

##### 法二：贪心 + 二分查找 #####

> 考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

新建数组 tails，用于保存最长上升子序列。

对原序列进行遍历，将每位元素二分插入 tails 中。

*  如果 tails 中元素都比它小，将它插到最后
 *  否则，用它覆盖掉比它大的元素中最小的那个。

总之，思想就是让 tails 中存储比较小的元素。这样，tails 未必是真实的最长上升子序列，但长度是对的。

tails 列表一定是严格递增的： 即当尽可能使每个子序列尾部元素值最小的前提下，子序列越长，其序列尾部元素值一定更大。

> 反证法证明： 当 k<i ，若 tails\[k\] >= tails\[i\] ，代表较短子序列的尾部元素的值 > 较长子序列的尾部元素的值。这是不可能的，因为从长度为 i 的子序列尾部倒序删除 i−1 个元素，剩下的为长度为 k 的子序列，设此序列尾部元素值为 v，则一定有 v < tails\[i\]（即长度为 k 的子序列尾部元素值一定更小）， 这和 tails\[k\] >= tails\[i\] 矛盾。

> 既然严格递增，每轮计算 tails\[k\]时就可以使用二分法查找需要更新的尾部元素值的对应索引 i。

**举个栗子：**  
例如：\[1 2 5 2 3 5 3 4 5\]

1.  以1结尾的最长上升子序列是\[1\]很显然
2.  接下来看以2结尾的最长上升子序列，显然2前面的最长上升且小于2的子序列，接上2是最长的，所以以2结尾的最长上升子序列是\[1 2\]
3.  再看5，是\[1 2 5\]
4.  以第二个2结尾的最长上升子序列是\[1 2’ 5\]
5.  以3结尾的显然是\[1 2’ 3\]所以用3把5覆盖（这一步是贪心，因为反正都是长度为"3"的前缀，尾巴越小，后面越容易接）
6.  再看下一个5，就变成\[1 2’ 3 5’\]
7.  再下一个3’把前面的3顶替了，\[1 2’ 3’ 5’\]
8.  再下一个4，接到3后面，因为贪心，把5顶替 \[1 2’ 3’ 4\]
9.  最后一个5’‘接上去，这个桶就看起来是：\[1 2’ 3’ 4 5’'\]

所以最长上升子序列长度为5，而且我们知道是第一个1，第二个2，第二个3，第一个4，第三个5，所以也可以找到序列位置

#### 代码：(Java) ####

##### 法一：动态规划 #####

##### 法二：贪心 + 二分查找 #####

public class LengthOfLIS {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int [] nums = {
        10,9,2,5,3,7,101,18};
    		System.out.println(lengthOfLIS(nums));
    		
    	}
    	
    	public static int lengthOfLIS(int[] nums) {
        
    		int n = nums.length;
    		
    		int len = 0;
    		
    		for(int i = 0; i < n; i++) {
        
    			int index = binarySearch(nums, len, nums[i]);
    			nums[index] = nums[i];
    			if(index == len) {
        
    				len++;
    			}
    		}
    		return len;
    	}
    
    	public static int binarySearch(int[] nums, int len, int num) {
        
    		// TODO Auto-generated method stub
    		int l = 0, h = len;
    		while(l < h) {
        
    			int mid = l + (h - l) / 2;
    			if(nums[mid] == num) {
        
    				return mid;
    			}else if(nums[mid] > num) {
        
    				h = mid;
    			}else {
        
    				l = mid + 1;
    			}
    		}
    		return l;
    	}
    }

##### 运行结果： #####

![在这里插入图片描述][894d1fb6bebd493189eadb7fa1df84e6.png]

##### 复杂度分析： #####

**法一：**

*  **时间复杂度**： O ( n 2 ) O(n^2) O(n2)，其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp\[i\] 时，需要 O(n) 的时间遍历 dp\[0…i−1\] 的所有状态，所以总时间复杂度为  O ( n 2 ) O(n^2) O(n2)。
 *  **空间复杂度**：O(n)，需要额外使用长度为 n 的 dp 数组。

**法二：**

*  **时间复杂度**：O(nlog⁡n)。数组 nums 的长度为 n，我们依次用数组中的元素去更新 当前最长子序列数组，而更新数组时需要进行 O(log⁡n) 的二分搜索，所以总时间复杂度为 O(nlog⁡n)。
 *  **空间复杂度**：O(1)，在原数组上记录，不需要额外空间。

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[894d1fb6bebd493189eadb7fa1df84e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/01eab20347e942299dc71580fdc2b13a.png
[Link 1]: https://leetcode.cn/problems/longest-increasing-subsequence/description/