最长递增子序列

BraumAce2024年10月3日约 1176 字大约 4 分钟

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

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

子序列：是可以通过从另一个数组删除或不删除某些元素，但不更改其余元素的顺序得到的数组。

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

思路

要求从所有递增子序列（LIS）中找到最长的序列，本质上是子集型问题。

有两种思路：

选或不选：为了比大小，需要知道上一个选的数字（即需要知道下标和值）
枚举选哪个：比较当前选的数字和下一个要选的数字（枚举前已确定值的范围，所以只需要知道下标）

综上，采用枚举选哪个的方式，只需要一个参数，更加好写。

具体的，枚举 nums[i] 作为 LIS 的末尾元素，那么需要枚举 nums[j] 作为 LIS 的倒数第二个元素，其中 j < i，且 nums[j] < nums[i]

对于回溯，需要确定三个问题：

子问题？以 nums[i] 结尾的 LIS 长度
当前操作？枚举 nums[j]
下一个子问题？以 nums[j] 结尾的 LIS 长度

即： $dfs(i) = max\{dfs(j)\} + 1$ ，条件为 j < i，且 nums[j] < nums[i]

可以得到递归的解法。但是由于每个子问题都需要进行枚举，会存在重复计算的问题，于是可以使用动态规划解决。得到状态转移表达式，即：

dp[i] = max(dp[i], dp[j]) + 1 \ \ (j < i, nums[j] < nums[i])

代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < i; j++){
                if (nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j]);
                }
            }
            
            dp[i]++;  // 表示选了当前的数
            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }
}

动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。

故时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。

二分优化

DP 时间复杂度优化

优化技巧：交换状态与状态值

$f[i]$ 表示末尾元素为 nums[i] 的最大上升子序列（LIS）的长度。

交换后得到：

$g[i]$ 表示长度为 $i + 1$ 的上升子序列（IS）的末尾元素的最小值。

当定义为最小值的时候，才更有机会去扩展 $g[i]$ 的长度

对于动态规划问题，如果想要优化时间复杂度，可以考虑交换状态与状态值。

比如 nums = [1, 6, 7, 2, 4, 5, 3]
g = [1]；
g = [1, 6]；
g = [1, 6, 7]；
g = [1, 2, 7]，遍历到 $2$ ，更新第一个大于 $2$ 的元素 g[1]，满足严格递增；
g = [1, 2, 4]，遍历到 $4$ ，同理更新；
g = [1, 2, 4, 5]；
g = [1, 2, 3, 5]，遍历到 $3$ ，同理更新。

可以得到思路：在 g 上用二分查找快速找到第一个大于 nums[i] 的下标 $j$ 。如果 $j$ 不存在，那么 nums[i] 直接加到 g 末尾，否则修改 g[j] 为 nums[i]。

需要开辟额外空间写法：

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> g = new ArrayList<>();
        for (int x : nums) {
            int j = lowerBound(g, x);
            if (j == g.size()) {
                g.add(x);   // >=x 的 g[j] 不存在
            } else {
                g.set(j, x);
            }
        }

        return g.size();
    }

    // 开区间写法
    private int lowerBound(List<Integer> g, int t) {
        int l = -1, r = g.size();   // 开区间 (left, right)
        while (l + 1 < r) {   // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = l + (r - l) / 2;
            if (g.get(mid) < t) {
                l = mid;   // 范围缩小到 (mid, right)
            } else {
                r = mid;   // 范围缩小到 (left, mid)
            }
        }
        return r;   // 或者 left+1
    }
}

时间复杂度为 $O(n long(n))$ ，空间复杂度为 $O(n)$ 。

进一步优化空间：

可以直接把 g 填入 nums 中，空间复杂度为 $O(1)$ ：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int ng = 0;   // g 的长度
        for (int x : nums) {
            int j = lowerBound(nums, ng, x);
            nums[j] = x;
            if (j == ng) {   // >=x 的 g[j] 不存在
                ng++;
            }
        }

        return ng;
    }

    // 开区间写法
    private int lowerBound(int[] nums, int r, int t) {
        int l = -1;   // 开区间 (left, right)
        while (l + 1 < r) {   // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = l + (r - l) / 2;
            if (nums[mid] < t) {
                l = mid;   // 范围缩小到 (mid, right)
            } else {
                r = mid;   // 范围缩小到 (left, mid)
            }
        }
        return r;   // 或者 left+1
    }
}

最长递增子序列

最长递增子序列

题意

思路

二分优化