LC 673. 最长递增子序列的个数

题目描述

这是 LeetCode 上的 673. 最长递增子序列的个数 ，难度为 中等。

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

1
2
3
4
5
输入: [1,3,5,4,7]

输出: 2

解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:
1
2
3
4
5
6
输入: [2,2,2,2,2]

输出: 5

解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

提示:

  • $1 <= nums.length <= 2000$
  • $-10^6 <= nums[i] <= 10^6$

序列 DP

与朴素的 LIS 问题（问长度）相比，本题问的是最长上升子序列的个数。

我们只需要在朴素 LIS 问题的基础上通过「记录额外信息」来进行求解即可。

在朴素的 LIS 问题中，我们定义 $f[i]$ 为考虑以 $nums[i]$ 为结尾的最长上升子序列的长度。 最终答案为所有 $f[0…(n - 1)]$ 中的最大值。

不失一般性地考虑 $f[i]$ 该如何转移：

  • 由于每个数都能独自一个成为子序列，因此起始必然有 $f[i] = 1$；
  • 枚举区间 $[0, i)$ 的所有数 $nums[j]$，如果满足 $nums[j] < nums[i]$，说明 $nums[i]$ 可以接在 $nums[j]$ 后面形成上升子序列，此时使用 $f[j]$ 更新 $f[i]$，即有 $f[i] = f[j] + 1$。

回到本题，由于我们需要求解的是最长上升子序列的个数，因此需要额外定义 $g[i]$ 为考虑以 $nums[i]$ 结尾的最长上升子序列的个数。

结合 $f[i]$ 的转移过程，不失一般性地考虑 $g[i]$ 该如何转移：

  • 同理，由于每个数都能独自一个成为子序列，因此起始必然有 $g[i] = 1$；
  • 枚举区间 $[0, i)$ 的所有数 $nums[j]$，如果满足 $nums[j] < nums[i]$，说明 $nums[i]$ 可以接在 $nums[j]$ 后面形成上升子序列，这时候对 $f[i]$ 和 $f[j] + 1$ 的大小关系进行分情况讨论：
    • 满足 $f[i] < f[j] + 1$：说明 $f[i]$ 会被 $f[j] + 1$ 直接更新，此时同步直接更新 $g[i] = g[j]$ 即可；
    • 满足 $f[i] = f[j] + 1$：说明找到了一个新的符合条件的前驱，此时将值继续累加到方案数当中，即有 $g[i] += g[j]$。

在转移过程，我们可以同时记录全局最长上升子序列的最大长度 $max$，最终答案为所有满足 $f[i] = max$ 的 $g[i]$ 的累加值。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        int max = 1;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1; g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }
            max = Math.max(max, f[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == max) ans += g[i];
        }
        return ans;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);
        int maxv = 1;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }
            maxv = max(maxv, f[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == maxv) ans += g[i];
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f, g = [1] * n, [1] * n
        maxv = 1
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if f[i] < f[j] + 1:
                        f[i], g[i] = f[j] + 1, g[j]
                    elif f[i] == f[j] + 1:
                        g[i] += g[j]
            maxv = max(maxv, f[i])
        ans = 0
        for i in range(n):
            if f[i] == maxv: ans += g[i]
        return ans

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function findNumberOfLIS(nums: number[]): number {
    const n = nums.length;
    let f = new Array(n).fill(1), g = new Array(n).fill(1);
    let max = 1;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (f[i] < f[j] + 1) {
                    f[i] = f[j] + 1;
                    g[i] = g[j];
                } else if (f[i] == f[j] + 1) {
                    g[i] += g[j];
                }
            }
        }
        max = Math.max(max, f[i]);
    }
    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (f[i] == max) ans += g[i];
    }
    return ans;
};

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$

LIS 问题的贪心解 + 树状数组

我们知道，对于朴素的 LIS 问题存在贪心解法，能够在 $O(n\log{n})$ 复杂度内求解 LIS 问题。

在贪心解中，我们会多开一个贪心数组 $q$，用来记录长度为 $len$ 的最长上升子序列的「最小结尾元素」为何值：$q[len] = x$ 代表长度为 $len$ 的最长上升子序列的最小结尾元素为 $x$。

可以证明 $q$ 存在单调性，因此每次确定 $nums[i]$ 可以接在哪个 $nums[j]$ 后面会形成最长上升子序列时，可以通过「二分」来找到满足 $nums[j] < nums[i]$ 的最大下标来实现。

对于本题，由于我们需要求最长上升子序列的个数，单纯使用一维的贪心数组记录最小结尾元素并不足以。

考虑对其进行扩展，期望能取到「最大长度」的同时，能够知道这个「最大长度」对应多少个子序列数量，同时期望该操作复杂度为 $O(\log{n})$。

我们可以使用「树状数组」维护二元组 $(len, cnt)$ 信息：

  1. 因为数据范围较大（$-10^6 <= nums[i] <= 10^6$），但数的个数为 $2000$，因此第一步先对 $nums$ 进行离散化操作；
  2. 在遍历 $nums$ 时，每次从树状数组中查询值严格小于 $nums[i]$ 离散值（利用 $nums[i]$ 离散化后的值仍为正整数，我们可以直接查询小于等于 $nums[i]$ 离散值 $-1$ 的值）的最大长度，及最大长度对应的数量；
  3. 对于流程 $2$ 中查得的 $(len, cnt)$，由于 $nums[i]$ 可以接在其后，因此首先长度加一，同时数量将 $cnt$ 累加到该离散值中。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    int n;
    int[][] tr = new int[2010][2];
    int lowbit(int x) {
        return x & -x;
    }
    int[] query(int x) {
        int len = 0, cnt = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            if (len == tr[i][0]) {
                cnt += tr[i][1];
            } else if (len < tr[i][0]) {
                len = tr[i][0];
                cnt = tr[i][1];
            }
        }
        return new int[]{len, cnt};
    }
    void add(int x, int[] info) {
        for (int i = x; i <= n; i += lowbit(i)) {
            int len = tr[i][0], cnt = tr[i][1];
            if (len == info[0]) {
                cnt += info[1];
            } else if (len < info[0]) {
                len = info[0];
                cnt = info[1];
            }
            tr[i][0] = len; tr[i][1] = cnt;
        }
    }
    public int findNumberOfLIS(int[] nums) {
        n = nums.length;
        // 离散化
        int[] tmp = nums.clone();
        Arrays.sort(tmp);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, idx = 1; i < n; i++) {
            if (!map.containsKey(tmp[i])) map.put(tmp[i], idx++);
        }
        // 树状数组维护 (len, cnt) 信息
        for (int i = 0; i < n; i++) {
            int x = map.get(nums[i]);
            int[] info = query(x - 1);
            int len = info[0], cnt = info[1];            
            add(x, new int[]{len + 1, Math.max(cnt, 1)});
        }
        int[] ans = query(n);
        return ans[1];
    }
}

  • 时间复杂度：$O(n\log{n})$
  • 空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.673 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。