题目描述(中等难度)
300、Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [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.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
最长上升子序列的长度。
解法一
比较经典的一道题,之前笔试也遇到过。最直接的方法就是动态规划了。
dp[i]
表示以第 i
个数字为结尾的最长上升子序列的长度。
求 dp[i]
的时候,如果前边的某个数 nums[j] < nums[i]
,那么我们可以将第 i
个数接到第 j
个数字的后边作为一个新的上升子序列,此时对应的上升子序列的长度就是 dp[j] + 1
。
可以从下边情况中选择最大的。
如果 nums[0] < nums[i]
,dp[0] + 1
就是 dp[i]
的一个备选解。
如果 nums[1] < nums[i]
,dp[1] + 1
就是 dp[i]
的一个备选解。
如果 nums[2] < nums[i]
,dp[2] + 1
就是 dp[i]
的一个备选解。
...
如果 nums[i-1] < nums[i]
,dp[i-1] + 1
就是 dp[i]
的一个备选解。
从上边的备选解中选择最大的就是 dp[i]
的值。
public int lengthOfLIS(int[] nums) { int n = nums.length; if (n == 0) { return 0; } int dp[] = new int[n]; int max = 1; for (int i = 0; i < n; i++) { dp[i] = 1; 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; }
时间复杂度:O(n²)
。
空间复杂度:O(1)
。
解法二
还有一种很巧妙的方法,最开始知道这个方法的时候就觉得很巧妙,但还是把它忘记了,又看了一遍 这里-time-with-explanation) 才想起来。
不同之处在于 dp
数组的定义。
dp[i]
表示长度为 i + 1
的所有上升子序列的末尾的最小值。
举个例子。
nums = [4,5,6,3] len = 1 : [4], [5], [6], [3] => tails[0] = 3 长度为 1 的上升子序列有 4 个,末尾最小的值就是 3 len = 2 : [4, 5], [5, 6] => tails[1] = 5 长度为 2 的上升子序列有 2 个,末尾最小的值就是 5 len = 3 : [4, 5, 6] => tails[2] = 6 长度为 3 的上升子序列有 1 个,末尾最小的值就是 6
有了上边的定义,我们可以依次考虑每个数字,举个例子。
nums = [10,9,2,5,3,7,101,18] 开始没有数字 dp = [] 1---------------------------- 10 9 2 5 3 7 101 18 ^ 先考虑 10, 只有 1 个数字, 此时长度为 1 的最长上升子序列末尾的值就是 10 len 1 dp = [10] 2---------------------------- 10 9 2 5 3 7 101 18 ^ 考虑 9, 9 比之前长度为 1 的最长上升子序列末尾的最小值 10 小, 更新长度为 1 的最长上升子序列末尾的值为 9 len 1 dp = [9] 3---------------------------- 10 9 2 5 3 7 101 18 ^ 考虑 2, 2 比之前长度为 1 的最长上升子序列末尾的最小值 9 小, 更新长度为 1 的最长上升子序列末尾的值为 2 len 1 dp = [2] 4---------------------------- 10 9 2 5 3 7 101 18 ^ 考虑 5, 5 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 此时可以扩展长度, 更新长度为 2 的最长上升子序列末尾的值为 5 len 1 2 dp = [2 5] 5---------------------------- 10 9 2 5 3 7 101 18 ^ 考虑 3, 3 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 向后考虑 3 比之前长度为 2 的最长上升子序列末尾的最小值 5 小, 更新长度为 2 的最长上升子序列末尾的值为 3 len 1 2 dp = [2 3] 6---------------------------- 10 9 2 5 3 7 101 18 ^ 考虑 7, 7 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 向后考虑 7 比之前长度为 2 的最长上升子序列末尾的最小值 3 大, 向后考虑 此时可以扩展长度, 更新长度为 3 的最长上升子序列末尾的值为 7 len 1 2 3 dp = [2 3 7] 7---------------------------- 10 9 2 5 3 7 101 18 ^ 考虑 101, 101 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 向后考虑 101 比之前长度为 2 的最长上升子序列末尾的最小值 3 大, 向后考虑 101 比之前长度为 3 的最长上升子序列末尾的最小值 7 大, 向后考虑 此时可以扩展长度, 更新长度为 4 的最长上升子序列末尾的值为 101 len 1 2 3 4 dp = [2 3 7 101] 8---------------------------- 10 9 2 5 3 7 101 18 ^ 考虑 18, 18 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 向后考虑 18 比之前长度为 2 的最长上升子序列末尾的最小值 3 大, 向后考虑 18 比之前长度为 3 的最长上升子序列末尾的最小值 7 大, 向后考虑 3 比之前长度为 4 的最长上升子序列末尾的最小值 101 小, 更新长度为 4 的最长上升子序列末尾的值为 18 len 1 2 3 4 dp = [2 3 7 18] 遍历完成,所以数字都考虑了,此时 dp 的长度就是最长上升子序列的长度
总结上边的规律,新来一个数字以后,我们去寻找 dp
中第一个比它大的值,然后将当前值更新为新来的数字。
如果 dp
中没有比新来的数字大的数,那么就扩展长度,将新来的值放到最后。
写代码的话,因为 dp
是一个动态扩容的过程,我们可以用一个 list
。但由于比较简单,我们知道 dp
最大的长度也就是 nums
的长度,我们可以直接用数组,然后自己记录当前数组的长度即可。
public int lengthOfLIS(int[] nums) { int n = nums.length; if (n == 0) { return 0; } int dp[] = new int[n]; int len = 0; for (int i = 0; i < n; i++) { int j = 0; // 寻找 dp 中第一个大于等于新来的数的位置 for (j = 0; j < len; j++) { if (nums[i] <= dp[j]) { break; } } // 更新当前值 dp[j] = nums[i]; // 是否更新长度 if (j == len) { len++; } } return len; }
上边花了一大段话讲这个解法,但是上边的时间复杂度依旧是 O(n²)
,当然不能满足。
这个解法巧妙的地方在于,通过上边 dp
的定义,dp
一定是有序的。我们要从一个有序数组中寻找第一个大于等于新来数的位置,此时就可以通过二分查找了。
public int lengthOfLIS(int[] nums) { int n = nums.length; if (n == 0) { return 0; } int dp[] = new int[n]; int len = 0; for (int i = 0; i < n; i++) { int start = 0; int end = len; while (start < end) { int mid = (start + end) >>> 1; if (dp[mid] < nums[i]) { start = mid + 1; } else { end = mid; } } dp[start] = nums[i]; if (start == len) { len++; } } return len; }
这样的话时间复杂度就是 O(nlog(n))
了。
总
解法一比较常规,比较容易想到。
解法二的话就很巧妙了,关键就是 dp
的定义使得 dp
是一个有序数组了。这种也不容易记住,半年前笔试做过这道题,但现在还是忘记了,但还是可以欣赏一下的,哈哈。