【LC】No300. 最长递增子序列

题目描述

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

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

提示：

• 1 <= nums.length <= 2500

• -104 <= nums[i] <= 104

进阶：

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

示例

示例 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

链接

思路

本题追加为 【LC75】No334. 递增的三元子序列 的补充题目，作为求递增子序列的更通常的问题。

依旧是很好理解的题目，没有背景设置，所以中译中环节省略。

本题求解最长递增子序列，可以将问题一步步拆解回退：求以 nums[i] 结尾的最长递增子序列，可以化为求解分别以 nums[0]...nums[i-1] 所有元素结尾的最长递增子序列中最大的那个，再判断 nums[i] 能否追加到其后。

子问题互有重叠，因此，最先想到的必然是动态规划。

解法一：动态规划

我们使用动态规划的思路进行思考。

思路

1、数组定义

我们将 dp[i] 定义为以 nums[i] 结尾的最长递增子序列的长度。

2、动态转移方程

在求得 dp[i] 之前，我们必然要求得 dp[0]...dp[i-1] 中最大的一个。设此为 dp[j] (j < i)，当 nums[i] > nums[j] 时，表示 nums[i] 可以添加在以 nums[j] 结尾的最长递增子序列之后，进而组成新的最长递增子序列。

此时有：dp[i] = Math.max(dp[i], dp[j] + 1) ( j < i && nums[j] < nums[i] )

3、初始状态

对于 nums 数组，每个元素最起码都可以单独成为子序列，所以 dp[i] 最小可取 1。

如此则：dp 数组全部填充 1 。

4、遍历顺序

本题取从左向右遍历。

5、返回值

返回 dp[i] 中的最大值。

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // 动态规划数组
        int[] dp = new int[len];
        // 遍历中顺带查找最大值
        int res = 0;
        // 对于每个元素都有其本身作为子序列，所以全设为1
        Arrays.fill(dp, 1);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新最大值
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

• 时间复杂度：O(n²)

• 空间复杂度：O(n)

解法二：贪心+二分

考虑一个贪心思想：

为了找到最长的递增子序列，我们应该让其中每个元素都尽可能地小，此时更长序列的可能性就越大。

解法一中额外数组维护的是最长递增子序列的长度，此时无法考虑贪心。那么我们换个思路，将额外数组的元素设置为最长递增子序列的结尾值。

即：设一个 tmp 数组，tmp[i] 表示长度为 i+1 的最长递增子序列的末尾值的最小值。

根据前面的贪心思想，此 tmp[i] 严格递增，我们只需要维护一个尽可能小的 tmp 即可。

依次遍历 nums 数组，判断当前 nums[i] 能否按照递增的顺序插入到 tmp 数组中。

如果找不到插入位置，则代表 nums[i] 可以追加在当前递增子序列的后面，此时递增子序列的长度加一；如果找到插入位置，即在 tmp 数组中，找到第一个比 nums[i] 大的数，将此位置更新为 nums[i]。此举使得 tmp 的每个元素都在遍历中寻求最小值，进而求得递增子序列的最长长度。

由于 tmp 数组有序，我们使用二分法减少空间复杂度，搜索区间为当前的最长递增子序列。

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] tmp = new int[len]; 
        // res用来记录当前的最长递增子序列的长度
        int res = 0;
        for (int i = 0; i < len; i++) {
            // 左闭右开区间 [0, res)
            int left = 0, right = res;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (tmp[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // 找到的left即为插入位置
            tmp[left] = nums[i];
            // 如果left等于当前长度，代表tmp中找不到插入位置，此时nums[i]是追加在tmp结尾的，所以递增子序列长度加一
            if (res == left) {
                res++;
            }
        }
        return res;
    }
}

• 时间复杂度：O(nlogn)，遍历数组 O(n)，二分查找 O(logn)

• 空间复杂度：O(n)