300. 最长递增子序列

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

进阶：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

平方时间复杂度的算法比较容易想，dp[i]表示以i结尾的最长的递增序列的长度，对于每个i都去看前面的下标，元素是否比自己小，小的话对应的dp值加一就是dp[i]的候选值。

优化到nlogn不太好想，dp状态的定义需要改一下，dp[i]表示所有长度为i+1的递增序列中最小的末尾元素。贪心地，如果我们希望dp[i]越小越好，这样可以在后面接尽可能更大的元素，比如，对于输入[2,5,3,4]，当遍历到5时，dp[1]为5，但是当遍历到3时，我们需要将dp[1]修改为3，表示[2,3]是更好的长度为2的序列，这样后面才可以接4。所以我们需要不断更新dp数组，同时可以发现，dp数组是严格递增的，因此可以使用二分来查找并进行更新。所以复杂度可以降下来。

代码

DP O(n^2)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

DP+二分 O(nlogn)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        // end为当前发现的最长的递增序列的长度
        int end = 0;
        for (int i = 0; i < n; i++) {
            int l = 0;
            int r = end;
            while (l < r) {
                int mid = l + (r - l) / 2;
                // 注意这里是<不是<= 因为找的是第一个不小于nums[i]的元素，不是大于的，后者会使dp数组不严格递增，从而出现相等的值
                if (dp[mid] < nums[i]) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            // l<end表示找到了一个不小于nums[i]的元素
            if (l < end) {
                dp[l] = nums[i];
            } else { // l==end 表示dp[0:end-1]的值都小于nums[i]，长度为end+1的递增序列产生了
                dp[end++] = nums[i];
            }
        }
        return end;
    }
}