LeetCode 300. Longest Increasing Subsequence
2020-06-09 08:20:00 # leetcode # core problems # dynamic programming

Problem

LeetCode 300. Longest Increasing Subsequence

1. 题目简述

给出一个未排序的整形数组，返回其最长递增子序列的长度。

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:

只需要长度，而不是具体的串

time complexity要在O(n ^ 2)以下

2. 算法思路

相关问题：

  1. 673. Number of Longest Increasing Subsequence

首先要注意我们只需要返回长度即可，这里不需要考虑找出最长的那个子串，只要找到该串的长度即可。

暴力搜索

我们先来看看最暴力的思路，我们对每个节点记录一个dp值，该值表示从0到当前位置的数字中，以当前数字为结尾的最长递增子序列的长度。每次新到达一个数字后，找到其前面的所有数字中，比它小的所有数字中dp值最大的数字（不能等于，等于就不叫递增了），找出该节点的dp值，加一，即为当前节点的dp值。

$$dp[i] = max(dp[i], dp[j] + 1) (for j in 0 to n - 1 and nums[j] < nums[i])$$

时间复杂度为O(n ^ 2)，因为每次都要去找前面所有的数字，很慢。

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
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        int ret = 0;

        for (int i = 0; i < nums.length; i++) {
            int maxDP = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] > maxDP) {
                    maxDP = dp[j];
                }
            }
            dp[i] = maxDP + 1;
            ret = Math.max(dp[i], ret)
        }

        return ret;
    }
}

二分查找（直接背的最优解）

这道题二分查找的思路特别难想，建议直接背下来。思路如下：

  1. 我们维护一个数组，初始化为长度为nums.length，首个元素为nums[0]，记录size = 1；
  2. 然后向后遍历每一个数字，二分法找到在当前数组中它应该在的位置pos（如果比当前末尾的数要大，那么就是在末尾后面一位；如果比第一个数要小，那么位置就是0）；
  3. 替换掉pos位置的数字。判断：如果pos == size，那么size++；
  4. 直至循环结束，最终的size就是我们的大小。

Attention：这里只有size是我们想要的，而我们维护的那个数组并不一定是！！！

那么为什么是这样呢？size是我们想要的我们这点很清楚，因为对于任何一个数字而言，它只有两种可能性：（1）替换掉当前数组中某个数字（2）将数字加到末尾的后一位，size++。

如果替换掉当前数组中的任何一个，其实并不会改变当前size的大小。如果在末尾添加一个比较大的数，size也的确是增加了，不会存在任何影响，那么问题就在于我们为什么要替换掉数字呢？其实是为了避免下面这种情况，我们举一个极端的例子。

nums = [20, 100, 2, 3, 4, 5, 10, 80]，很明显，最终答案应该是6，如果我们不进行替换，那么我们就会发现从2以后好几个数字完全插不进去整个数组，因为他们都太小了，着很明显不是我们想要的，所以只有替换了，才能保证我们对于后面的查找判断不受影响。

那么为什么我们最后得到的不一定是我们最长的子序列呢？那是因为我们不一定能够替换完全。什么意思呢？我们再举个例子：nums = [20, 100, 2]和nums = [20, 100, 2, 3]，是不是好像明白了些什么？

其实，我们的目的是保证我们当前维护的这个最长递增序列的每个数的值尽可能保持小，如果后面有更小的序列我们就替换掉它，但是有可能在替换的过程中值替换了一半，所以并不保证最终得到的就是一个合法的最长递增子序列。

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
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] arr = new int[nums.length];
        int size = 1;
        arr[0] = nums[0];

        for (int num : nums) {
            // 找到num的位置，二分法找到比num大的最小的数。而且这里注意闭区间r和size的关系。
            int l = 0, r = size - 1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (arr[m] >= num) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            arr[l] = num;
            if (l == size) {
                size++;
            }
        }

        return size;
    }
}
Prev
2020-06-09 08:20:00 # leetcode # core problems # dynamic programming
Next