题目描述(中等难度)

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 是一个有序数组了。这种也不容易记住,半年前笔试做过这道题,但现在还是忘记了,但还是可以欣赏一下的,哈哈。

results matching ""

    No results matching ""