题目描述(中等难度)

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 ""