LeetCode 300. Longest Increasing Subsequence[Medium]

发表于 更新于 阅读次数：

题目链接：https://leetcode.com/problems/longest-increasing-subsequence/

题解链接：https://leetcode.com/articles/longest-increasing-subsequence/

题目

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

Example:

1
2
3
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(n^2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

解法1：蛮力法

思路

递归的方式，从第一个数字开始遍历，遍历每一个数字的时候，都存在两种情况，当前数字比最大递增字串中的最后一个数字大或者比最后一个数字小。如果当前数字比最长递增子串的最后一个数字小，那么当前数字肯定不能加入到最长递增子串中。但是如果当前数字比最长的最后一个数字大，那么可以把当前数字加入到最长递增字串中，也可以不加入。因为存在这么一种情况，当前位置的数字特别大，如果把当前位置的数字加入到最长递增字串中，后边就再也无法增加数字了。但是如果不把当前数字加入到最长递增子串中，那么后边还能继续添加其他的数字。

判断当前数字和当前最长递增子串的最后一个数字的关系，如果比前一个数字更大，那么下一步就算一下包含当前数字和不包含当前数字的情况。如果比前一个数字小，那么下一步就计算一下不包含当前数字的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int lengthOfLIS(int[] nums) {
        return lengthOfLIS(nums, Integer.MIN_VALUE, 0);
    }

    public int lengthOfLIS(int[] nums, int prev, int curpos) {
        if (curpos == nums.length) {
            return 0;
        }

        int includeCurrentElement = 0;
        if (nums[curpos] > prev) {
            includeCurrentElement = 1 + lengthOfLIS(nums, nums[curpos], curpos + 1);
        }

        int notIncludeCurrentElement = lengthOfLIS(nums, prev, curpos + 1);
        return Math.max(includeCurrentElement, notIncludeCurrentElement);
    }
}

复杂度分析

时间复杂度：$O(2^n)$

空间复杂度：$O(n^2)$

解法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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[][] cache = new int[nums.length + 1][nums.length];
        for (int[] l : cache) {
            Arrays.fill(l, -1);
        }
        return lengthOfLIS(nums, -1, 0, cache);
    }

    /**
     *
     * @param nums
     * @param prevIndex
     * @param curIndex 表示当前的元素
     * @param cache
     * @return
     */
    public int lengthOfLIS(int[] nums, int prevIndex, int curIndex, int[][] cache) {
        if (curIndex == nums.length) {
            // curIndex 已经越界了，返回
            return 0;
        }

        if (cache[prevIndex + 1][curIndex] >= 0) {
            return cache[prevIndex + 1][curIndex];
        }

        int taken = 0;
        if (prevIndex < 0 || nums[curIndex] > nums[prevIndex]) {
            // prevIndex 小于 0 表示是第一个数字
            // 把当前元素算入到最长子串中，所以要加 1
            taken = 1 + lengthOfLIS(nums, curIndex, curIndex + 1, cache);
        }

        int notTaken = lengthOfLIS(nums, prevIndex, curIndex + 1, cache);
        cache[prevIndex + 1][curIndex] = Math.max(taken, notTaken);
        return cache[prevIndex + 1][curIndex];
    }
}

参考：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/chao-xiang-xi-tu-jie-di-gui-dong-tai-gui-hua-er-fe/

解法3：动态规划

思路：利用一个临时数组 dp[]，dp[i] 表示截止到当前位置的最大递增子串的长度。这样，假如向原数组后边继续追加新的数字，只需要把新数字和数组中前边位置的数字作比较，只要比前边的数字大，就表示当前位置的最大递增字串的长度至少是 dp[i] + 1 ，把所有数字遍历下来就可以知道当前位置的最大递增字串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Problem300Solution3 {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

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

        return globalMaxLength;
    }
}

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/chao-xiang-xi-tu-jie-di-gui-dong-tai-gui-hua-er-fe/

复杂度分析

解法4：贪心算法（二分查找）

思路：既然要求的是最大递增子串的长度，那么就找到其中一个最长递增子串。从第一个数字开始遍历，只要能形成递增数列就加到末尾，如果比当前的最长递增子串的最大值要小，就替换掉最长递增子串中的一个刚好比这个数字小的数字。

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

        ArrayList<Integer> currentLIS = new ArrayList<Integer>();
        currentLIS.add(nums[0]);
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > currentLIS.get(currentLIS.size() - 1)) {
                currentLIS.add(nums[i]);
                continue;
            }

            int begin = 0;
            int end = currentLIS.size() - 1;
            while (begin <= end) {
                int mid = begin + (end - begin) / 2;
                if (nums[i] < currentLIS.get(mid)) {
                    end = mid - 1;
                } else if (nums[i] > currentLIS.get(mid)) {
                    begin = mid + 1;
                } else {
                    begin = mid;
                    break;
                }
            }
            currentLIS.set(begin, nums[i]);
        }
        return currentLIS.size();
    }
}

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/chao-xiang-xi-tu-jie-di-gui-dong-tai-gui-hua-er-fe/

复杂度分析

时间复杂度：$O(nlog n)$

空间复杂度：$O(n)$

参考资料

  1. LeetCode 300. Longest Increasing Subsequence 最长递增子序列 - Grandyang - 博客园