题目描述（中等难度）

300、Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

  1. Input: [10,9,2,5,3,7,101,18]
  2. Output: 4 
  3. 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] 的值。

  1. public int lengthOfLIS(int[] nums) {
  2.     int n = nums.length;
  3.     if (n == 0) {
  4.         return 0;
  5.     }
  6.     int dp[] = new int[n];
  7.     int max = 1;
  8.     for (int i = 0; i < n; i++) {
  9.         dp[i] = 1;
  10.         for (int j = 0; j < i; j++) {
  11.             if (nums[j] < nums[i]) {
  12.                 dp[i] = Math.max(dp[i], dp[j] + 1);
  13.             }
  14.         }
  15.         max = Math.max(max, dp[i]);
  16.     }
  17.     return max;
  18. }

时间复杂度：O(n²)。

空间复杂度：O(1)。

解法二

还有一种很巧妙的方法，最开始知道这个方法的时候就觉得很巧妙，但还是把它忘记了，又看了一遍 这里-time-with-explanation) 才想起来。

不同之处在于 dp 数组的定义。

dp[i] 表示长度为 i + 1 的所有上升子序列的末尾的最小值。

举个例子。

  1. nums = [4,5,6,3]
  2. len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
  3. 长度为 1 的上升子序列有 4 个，末尾最小的值就是 3
  5. len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
  6. 长度为 2 的上升子序列有 2 个，末尾最小的值就是 5
  8. len = 3   :      [4, 5, 6]            => tails[2] = 6
  9. 长度为 3 的上升子序列有 1 个，末尾最小的值就是 6

有了上边的定义，我们可以依次考虑每个数字，举个例子。

  1. nums = [10,9,2,5,3,7,101,18]
  3. 开始没有数字
  4. dp = []
  6. 1----------------------------
  7. 10  9  2  5  3  7  101  18
  8. ^   
  10. 先考虑 10, 只有 1 个数字, 此时长度为 1 的最长上升子序列末尾的值就是 10
  11. len   1
  12. dp = [10]
  14. 2----------------------------
  15. 10  9  2  5  3  7  101  18
  16.     ^  
  17. 考虑 9, 9 比之前长度为 1 的最长上升子序列末尾的最小值 10 小, 更新长度为 1 的最长上升子序列末尾的值为 9
  18. len   1
  19. dp = [9]    
  21. 3----------------------------
  22. 10  9  2  5  3  7  101  18
  23.        ^  
  24. 考虑 2, 2 比之前长度为 1 的最长上升子序列末尾的最小值 9 小, 更新长度为 1 的最长上升子序列末尾的值为 2
  25. len   1
  26. dp = [2]    
  28. 4----------------------------
  29. 10  9  2  5  3  7  101  18
  30.           ^  
  31. 考虑 5, 
  32. 5 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 
  33. 此时可以扩展长度, 更新长度为 2 的最长上升子序列末尾的值为 5
  34. len   1  2
  35. dp = [2  5]   
  37. 5----------------------------
  38. 10  9  2  5  3  7  101  18
  39.              ^  
  40. 考虑 3, 
  41. 3 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 向后考虑
  42. 3 比之前长度为 2 的最长上升子序列末尾的最小值 5 小, 更新长度为 2 的最长上升子序列末尾的值为 3
  43. len   1  2
  44. dp = [2  3]   
  46. 6----------------------------
  47. 10  9  2  5  3  7  101  18
  48.                 ^  
  49. 考虑 7, 
  50. 7 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 向后考虑
  51. 7 比之前长度为 2 的最长上升子序列末尾的最小值 3 大, 向后考虑
  52. 此时可以扩展长度, 更新长度为 3 的最长上升子序列末尾的值为 7
  53. len   1  2  3
  54. dp = [2  3  7]  
  56. 7----------------------------
  57. 10  9  2  5  3  7  101  18
  58.                     ^  
  59. 考虑 101, 
  60. 101 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 向后考虑
  61. 101 比之前长度为 2 的最长上升子序列末尾的最小值 3 大, 向后考虑
  62. 101 比之前长度为 3 的最长上升子序列末尾的最小值 7 大, 向后考虑
  63. 此时可以扩展长度, 更新长度为 4 的最长上升子序列末尾的值为 101
  64. len   1  2  3   4
  65. dp = [2  3  7  101]  
  67. 8----------------------------
  68. 10  9  2  5  3  7  101  18
  69.                         ^  
  70. 考虑 18, 
  71. 18 比之前长度为 1 的最长上升子序列末尾的最小值 2 大, 向后考虑
  72. 18 比之前长度为 2 的最长上升子序列末尾的最小值 3 大, 向后考虑
  73. 18 比之前长度为 3 的最长上升子序列末尾的最小值 7 大, 向后考虑
  74. 3 比之前长度为 4 的最长上升子序列末尾的最小值 101 小, 更新长度为 4 的最长上升子序列末尾的值为 18
  75. len   1  2  3   4
  76. dp = [2  3  7   18] 
  78. 遍历完成，所以数字都考虑了，此时 dp 的长度就是最长上升子序列的长度

总结上边的规律，新来一个数字以后，我们去寻找 dp 中第一个比它大的值，然后将当前值更新为新来的数字。

如果 dp 中没有比新来的数字大的数，那么就扩展长度，将新来的值放到最后。

写代码的话，因为 dp 是一个动态扩容的过程，我们可以用一个 list 。但由于比较简单，我们知道 dp 最大的长度也就是 nums 的长度，我们可以直接用数组，然后自己记录当前数组的长度即可。

  1. public int lengthOfLIS(int[] nums) {
  2.     int n = nums.length;
  3.     if (n == 0) {
  4.         return 0;
  5.     }
  6.     int dp[] = new int[n];
  7.     int len = 0;
  8.     for (int i = 0; i < n; i++) {
  9.         int j = 0;
  10.         // 寻找 dp 中第一个大于等于新来的数的位置
  11.         for (j = 0; j < len; j++) {
  12.             if (nums[i] <= dp[j]) {
  13.                 break;
  14.             }
  15.         }
  16.         // 更新当前值
  17.         dp[j] = nums[i];
  18.         // 是否更新长度
  19.         if (j == len) {
  20.             len++;
  21.         }
  22.     }
  23.     return len;
  24. }

上边花了一大段话讲这个解法，但是上边的时间复杂度依旧是 O(n²)，当然不能满足。

这个解法巧妙的地方在于，通过上边 dp 的定义，dp 一定是有序的。我们要从一个有序数组中寻找第一个大于等于新来数的位置，此时就可以通过二分查找了。

  1. public int lengthOfLIS(int[] nums) {
  2.     int n = nums.length;
  3.     if (n == 0) {
  4.         return 0;
  5.     }
  6.     int dp[] = new int[n];
  7.     int len = 0;
  8.     for (int i = 0; i < n; i++) {
  9.         int start = 0;
  10.         int end = len;
  11.         while (start < end) {
  12.             int mid = (start + end) >>> 1;
  13.             if (dp[mid] < nums[i]) {
  14.                 start = mid + 1;
  15.             } else {
  16.                 end = mid;
  17.             }
  18.         }
  19.         dp[start] = nums[i];
  20.         if (start == len) {
  21.             len++;
  22.         }
  23.     }
  24.     return len;
  25. }

这样的话时间复杂度就是 O(nlog(n)) 了。

总

解法一比较常规，比较容易想到。

解法二的话就很巧妙了，关键就是 dp 的定义使得 dp 是一个有序数组了。这种也不容易记住，半年前笔试做过这道题，但现在还是忘记了，但还是可以欣赏一下的，哈哈。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情