300. 最长递增子序列

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • LIS

思路

一、问题描述

给定一个整数数组 nums，要求返回其 最长递增子序列（LIS）的长度。子序列是由数组中某些元素构成的，且这些元素的顺序与原数组中的顺序一致。

二、动态规划方法（DP）

1. 初始值

定义状态数组 f[i] 表示以第 i 个元素为结尾的 最长递增子序列的长度。我们初始化每个位置的值为 1，因为每个元素本身就是一个长度为 1 的递增子序列。

1
f[i] = 1

2. 状态转移方程

对于每个 i（从 1 到 n），我们尝试所有 j < i 的元素，检查 nums[i-1] > nums[j-1] 是否成立。若成立，表示 nums[i-1] 可以接在 nums[j-1] 的后面构成递增子序列，因此我们有：

1
f[i] = max(f[i], f[j] + 1)

该公式的意思是，如果 nums[i-1] > nums[j-1]，则 nums[i-1] 可以延长以 nums[j-1] 为结尾的递增子序列，我们更新 f[i]。

最后的答案即为 f 数组中的最大值，即：

1
res = max(res, f[i])

3. 最终答案

最终 res 就是 f 数组中的最大值，表示数组 nums 的最长递增子序列的长度。

4. 代码实现：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 2550;
    int lengthOfLIS(vector<int>& nums) {
        int f[maxn], n = nums.size(), res = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = 1;
            for (int j = i - 1; j >= 1; --j) {
                if (nums[i - 1] > nums[j - 1])
                    f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }
        return res;
    }
};

5. 时间复杂度分析

时间复杂度：O(n^2)，因为对于每个元素 i，我们需要扫描前面的元素 j 来更新 f[i]。

空间复杂度：O(n)，使用了一个 f 数组来存储每个位置的递增子序列长度。

1. 贪心策略

贪心的核心思想是维护一个数组 f，该数组记录了 每个长度的递增子序列的最小末尾元素。例如：

  • f[k] 记录长度为 k+1 的递增子序列的 最小结尾元素。

我们遍历数组 nums 中的每个元素 x，然后使用 二分查找 来确定 x 在 f 中的位置：

  • 如果 x 大于 f 中的所有元素，则将 x 添加到 f 的末尾；
  • 如果 x 小于等于 f 中的某个元素，则将该位置的元素更新为 x，保持 f 数组尽量小，能够让后续的元素有更大的接入空间。

2. 二分查找的应用

我们使用 lower_bound 函数在 f 数组中查找第一个大于等于 x 的位置。如果找到了这个位置，我们替换该位置的元素；如果没有找到，则将 x 添加到 f 数组的末尾。

3. 数组单调递增的性质

f 数组始终保持单调递增的性质，即每个位置的元素都不小于前一个元素。这是因为我们每次都保持最小的结尾元素，而二分查找确保我们 最小化了每个子序列的结尾。

4. 点阵图示例

我们以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例，展示 f 数组的变化。

i 当前元素 x f 数组状态 解释
1 10 [10] 10 是第一个元素，直接加入 f
2 9 [9] 9 < 10，用 9 替换掉 10
3 2 [2] 2 < 9，用 2 替换掉 9
4 5 [2, 5] 5 > 2，加入 5
5 3 [2, 3] 3 > 2，替换掉 5，保持最小结尾值
6 7 [2, 3, 7] 7 > 3，加入 7
7 101 [2, 3, 7, 101] 101 > 7，加入 101
8 18 [2, 3, 7, 18] 18 < 101，用 18 替换掉 101

最终 f = [2, 3, 7, 18]，其大小为 4，即 LIS 的长度为 4。

5. 代码实现：贪心 + 二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    static const int maxn = 2550;
    int lengthOfLIS(vector<int>& nums) {
        vector<int> f;
        for (int& x : nums) {
            auto it = lower_bound(f.begin(), f.end(), x);
            if (it == f.end())
                f.push_back(x);
            else
                *it = x;
        }
        return f.size();
    }
};

6. 时间复杂度分析

时间复杂度：O(n log n)，因为我们使用二分查找来维护 f 数组。 空间复杂度：O(n)，我们使用了一个 f 数组来记录递增子序列的最小结尾元素。