300. 最长上升子序列

leetcode 300. 最长上升子序列

题目：300. 最长上升子序列

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

示例:

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

说明:

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

方法一：动态规划

思路：动态规划，状态转移方程为：dp[i] = max(dp[i], dp[j] + 1);（nums[i] > nums[j]）。dp[i]表示以nums[i]结尾的最长上升子序列的长度。

运行数据：执行用时：14 ms，内存消耗：36.8 MB

复杂度分析：

• 时间复杂度：O(n^2)，n为nums的元素个数，两层循环。
• 空间复杂度：O(n)，n为nums的元素个数，dp消耗的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// LeetCode指定调用方法 
public int lengthOfLIS(int[] nums) {
		
    int n = nums.length;
    int [] dp = new int[n];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int max = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                max = Math.max(max, dp[j] + 1);
            }
        }
        dp[i] = max;
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

方法二：贪心 + 二分查找

思路：贪心 + 二分查找，通过一次循环遍历nums，用tails存储当前最长最小上升子序列，每次遍历一个nums数组新元素num，通过二分查找在当前tails中查询与num最接近的元素tails[m]，如果num大于tails[m]则将num覆盖tails[m + 1]，否则将num覆盖tails[m]，从而保持tails是当前的最长最小上升子序列，如果num大于tails[m]且tails[m]刚好是最后一个元素，则会将num储存在tails[m + 1]上，且当前的最长最小上升子序列长度将会加一。遍历完nums后，tails中存储元素个数即为最长上升子序列长度。

运行数据：执行用时：1 ms，内存消耗：37 MB

复杂度分析：

• 时间复杂度：O(n * log(n))，n为nums的元素个数，遍历nums的时间复杂度为O(n)，二分查找的时间复杂度为O(log(n))。
• 空间复杂度：O(n)，n为nums的元素个数，tails消耗的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// LeetCode指定调用方法 
public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int res = 0;
    for(int num : nums) {
        int i = 0, j = res;
        while (i < j) {
            int m = (i + j) / 2;
            if (tails[m] < num) i = m + 1;
            else j = m;
        }
        tails[i] = num;
        if (j == res) res++;
    }
    return res;
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！