[LeetCode] 300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

最长递增子序列。

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路一 - dp

注意子序列 subsequence 和子串 substring 的不同,子序列 subsequence 是可以断开的,只要相对顺序是上升的即可。这个题有两种做法,一是动态规划,一是动态规划基础上的二分。Longest Increasing Subsequence (LIS) 也是一类常考的题型。

首先是动态规划。设 dp[i] 是以 nums[i] 为结尾的子序列的最大长度。首先初始化的时候,dp 数组的每一个元素都是 1,因为如果以当前元素为结尾,不看其他元素的话,子序列最大长度就是 1。

更新 dp 数组的方法是用双指针,用一个指针 i 去遍历 input 的时候,同时设置另一个指针 j 扫描 j - i 的范围,如果在 j - i 的范围中有数字 nums[j] < nums[i],则 dp[i] = Math.max(dp[i], dp[j] + 1)

最后要找的结果是 dp 数组中的最大值。动图帮助理解

复杂度

时间O(n^2)
空间O(n)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int lengthOfLIS(int[] nums) {
int max = 0;
int[] dp = new int[nums.length];
// 初始化为1,因为每个以nums[i]结尾的子数组的长度都起码是1
Arrays.fill(dp, 1);
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);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}

思路二 - 在dp上的二分查找

dp 基础上的二分法。创建一个和 input 等长的 input 数组 dp,这个 dp 数组是我们维护的一个 tails 列表,其中每个元素 tails[k] 的值代表长度为 k + 1 的子序列尾部元素的值。

把第一个数字放入 dp 数组,从第二个数字开始,用二分法去找到这个数字应该被放入的位置。这里的 dp 数组记录的是实打实的数字,注意最后 dp 数组中的结果可能并不一定是一个正确的子序列,但是长度是对的。

遍历input,

  • 如果遇到的数字比 DP 数组里面最大的数字还要大,就加到 DP 数组的末端,len++,这也是唯一扩大 DP 数组 size 的办法
  • 如果遇到的数字小于 DP 数组中的最大数字,则需要将这个数字通过二分法的方式放到 DP 数组中他该存在的位置,但是只能替换,而不是插入。
    • 举个例子,如果你现在有数组[1, 3, 5],当你遇到一个4的时候,你只有通过把 5 替换成 4,才有可能将数组的最大值变小,从而有机会在数组的最后加入更多的值

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

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
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
// dp数组的下标
int index = 0;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
// 找到第一个大于等于nums[i]的index在哪里
int pos = helper(dp, index, nums[i]);
if (nums[i] < dp[pos]) {
dp[pos] = nums[i];
}
if (pos > index) {
index++;
dp[index] = nums[i];
}
}
return index + 1;
}

private int helper(int[] dp, int index, int val) {
int left = 0;
int right = index;
while (left <= right) {
int mid = left + (right - left) / 2;
if (dp[mid] == val) {
return mid;
} else if (dp[mid] < val) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}

[LeetCode] 300. Longest Increasing Subsequence
https://shurui91.github.io/posts/248222139.html
Author
Aaron Liu
Posted on
June 6, 2020
Licensed under