此问题第二种贪心解法可能不容易理解，可以结合图片和代码一起，会好理解很多！有问题可以评论哈！🎉

最长递增子序列

题目描述

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

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

数据样例

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • $1 \leq nums.length \leq 2500$
  • $-10 ^ 4 \leq nums[i] \leq 10 ^ 4$

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

动态规划 - $O(N ^ 2)$

动态规划

状态表示：$f[i]$ 表示以 $i$ 结尾的最长严格单调递增子序列的长度。

状态计算：

我们考虑前面所有可以将 $i$ 拼接到后面的子序列，我们知道，为了保证子序列是严格单调递增的，那么:

$i$ 可以拼接到前面序列中比 $nums[i]$ 小的的子序列后面。

因此状态转移方程为：
$$
f[i] = max(f[i], f[j] + 1), nums[j] < nums[i]
$$

时间复杂度 - $O(N ^ 2)$

每次状态计算需要遍历前面所有状态，因此时间复杂度是：$O(N ^ 2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func lengthOfLIS(nums []int) int {
    n := len(nums)
    f, res := make([]int, n), 0
    for i := 0; i < n; i++ {
        // 初始化为 1，表示当前元素单独构成一个长度为 1 的严格递增的子序列
        f[i] = 1
        // 枚举前面所有的严格递增的子序列，如果小于当前的数，那么可以将当前数拼接到对应子序列后面
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                f[i] = max(f[i], f[j] + 1)
            }
        }
        res = max(res, f[i])
    }
    return res
}

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

贪心，二分 - $O(N * log(N))$

贪心思想

考虑当前第 $i$ 个字符的前面所有可能的严格递增子序列，按照 序列长度 进行分类，我们以第一个样例为例来说明这个过程：

PS：每个序列长度里面的序列我们只选择 末尾元素最小 的序列。

[10,9,2,5,3,7,101,18]，假设 $i = 4, nums[i] = 3$，此时划分结果如下：

  • 长度为 $1$: 2 - 可能的序列有：10, 9, 2, 5, 3，末尾元素最小的序列是 2
  • 长度为 $2$：2 3 - 可能的序列有：2 5, 2 3，末尾元素最小的序列是 2 3（因为 $3 < 5$）
  • 长度为 $3$: 不存在长度为 $3$ 的严格递增的子序列

此时我们总结一下上述 算法过程：

  • 依次从左往右枚举序列
  • 如果比前面 最长的序列 中的末尾元素 大，那么可以得到一个更长的序列
  • 否则：当前元素替换掉前面序列中末尾元素比当前元素大的序列的末尾元素（贪心）

二分

按照上述算法过程，我们可以利用数组来模拟这个过程（参考下面图理解）：

  • f[i] 表示长度为 i 的严格递增的子序列 末尾元素最小值
  • len 标记当前最长严格递增子序列的长度
  • 依次从左至右枚举序列：
    • 如果 nums[i] > f[len]，那么我们得到一个更长的子序列：f[++len] = nums[i]
    • 否则，我们从 f[1], f[2], ..., f[len] 寻找第一个大于等于 nums[i] 的序列长度，假设为 f[x]，那么贪心考虑 f[x] = nums[i]

f[] 数组是递增的，可以利用二分寻找大于等于 nums[i] 的 f[x]

  • 每次 nums[i] > f[len] 的时候添加一个更大的元素，此时 f 是递增的
  • 每次替换掉前面某个序列末尾元素后，不影响单调性

PS：这里如果不理解，可以评论或者私信呀！

时间复杂度 - $O(N * log(N))$

  • 枚举序列，复杂度为 $O(N)$
  • 每次二分找到前面大于等于当前 nums[i] 的位置：$O(log(N))$

因此整体时间复杂度为：$O(N * log(N))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lengthOfLIS(nums []int) int {
    n := len(nums)
    // 定义数组 f[i]：表示长度为 i 的严格递增的子序列 末尾元素最小值
    // len 为当前最长严格递增子序列长度，初始化为 0
    f, len := make([]int, n + 1), 0
    f[len] = -1e9
    for i := 0; i < n; i++ {
        // 如果当前元素比最长的严格递增子序列末尾元素大，那么可以得到一个更长的子序列
        if nums[i] > f[len] { 
            len++
            f[len] = nums[i]
        } else {
            // 否则，二分找到大于等于当前元素 nums[i] 的值（某个子序列末尾元素的值），将其替换掉（贪心思想）
            p := sort.Search(len, func(j int) bool {
                return f[j] >= nums[i]
            })
            f[p] = nums[i]
        }
    }
    // 最后枚举完毕，len 表示整个序列最长严格递增子序列的长度，即为答案
    return len
}

func max(a, b int) int { if a < b {return b}; return a}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1, 0);
        int len = 0; f[len] = INT_MIN;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > f[len]) f[++len] = nums[i];
            else {
                int p = lower_bound(f.begin(), f.begin() + len, nums[i]) - f.begin();
                f[p] = nums[i];
            }
        }
        return len;
    }
};