友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 <= nums.length <= 2500 -
-104 <= nums[i] <= 104
进阶：
-
你能将算法的时间复杂度降低到 \(O(n*log(n))\) 吗?
思路分析
最简单易懂，也是最容易想到的解法就是：将指定数 nums[i] 与前面的每一个数都去比较一下，记录一下大于的次数。使用 dp[k] 记录以 k 结尾时的最大增长子序列长度。
动态规划+二分查找的算法还需要再仔细研究一下。还是有些懵逼！
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
* Runtime: 2 ms, faster than 76.15% of Java online submissions for Longest Increasing Subsequence.
*
* Memory Usage: 42.1 MB, less than 5.00% of Java online submissions for Longest Increasing Subsequence.
*
* Copy from: https://leetcode.cn/problems/longest-increasing-subsequence/solutions/24173/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/[最长上升子序列（动态规划 + 二分查找，清晰图解） - 最长上升子序列 - 力扣（LeetCode）]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-23 10:24
*/
public int lengthOfLIS(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return 0;
}
int[] tails = new int[nums.length];
int result = 0;
for (int num : nums) {
int i = 0, j = result;
while (i < j) {
int m = (i + j) / 2;
if (tails[m] < num) {
i = m + 1;
} else {
j = m;
}
}
tails[i] = num;
if (result == j) {
result++;
}
}
return result;
}
/**
* Runtime: 2 ms, faster than 76.15% of Java online submissions for Longest Increasing Subsequence.
*
* Memory Usage: 42.1 MB, less than 5.00% of Java online submissions for Longest Increasing Subsequence.
*
* Copy from: https://leetcode.com/problems/longest-increasing-subsequence/solution/[Longest Increasing Subsequence solution - LeetCode]
*/
public int lengthOfLISDPBS(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, len, num);
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == len) {
len++;
}
}
return len;
}
/**
* Runtime: 56 ms, faster than 5.76% of Java online submissions for Longest Increasing Subsequence.
*
* Memory Usage: 43.2 MB, less than 5.00% of Java online submissions for Longest Increasing Subsequence.
*
* Copy from: https://leetcode.com/problems/longest-increasing-subsequence/solution/[Longest Increasing Subsequence solution - LeetCode]
*/
public int lengthOfLISDP(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int result = 1;
for (int i = 1; i < nums.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
result = Math.max(result, dp[i]);
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-08 16:55:25
*/
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
// 每个数都是一个子序列，满足严格递增
Arrays.fill(dp, 1);
int result = 1;
// 双重循环等于将指定数nums[i]与前面的每一个数都去比较一下
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
result = Math.max(result, dp[i]);
}
}
return result;
}