LeetCode300-最长上升子序列

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/longest-increasing-subsequence/

中文链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/

题目详述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

1
2
3
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

题目详解

动态规划。

  • dp[i] 表示以 nums[i] 结尾最长递增子序列的长度。
  • 则 dp[i] = max{ dp[j] + 1 | j < i, nums[j] < nums[i]}。
  • 最终的最长递增子序列的长度是 dp 数组中的最大值。
  • 时间复杂度为 O(n2) 。
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 LeetCode_00300 {

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = dp[0];
        for (int d : dp) {
            res = Math.max(res, d);
        }
        return res;
    }
}

可以运用二分查找将时间复杂度从 O(n2) 降为 O(n log n) 。

  • dp[i] 表示长度为 i + 1 的最长递增子序列的最后一个元素。
  • 对于数组 nums 的一个元素 x，
  • 如果它大于 dp 数组所有的值，那么把它添加到 dp 后面，表示最长递增子序列长度加 1；
  • 如果 dp[i - 1] < x <= dp[i]，那么更新 dp[i] = x。
  • 最终的最长递增子序列的长度就是 dp 数组的实际长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00300 {

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            // 找到第一个大于等于 num 的位置
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                ++len;
            }
        }
        return len;
    }
}