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

发表于 2025-12-26 分类于力扣阅读次数： Waline：本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

LIS
二分
贪心
前缀和

思路

1. 问题描述与目标

给定一个整数序列 \[ \text{nums} = [a_1, a_2, \dots, a_n] \] 需要同时求出：

最长递增子序列（LIS）的最大长度
达到该最大长度的 不同递增子序列的个数

本题的难点不在于“长度”，而在于“计数”。

2. 经典 LIS（长度）问题的回顾

2.1 贪心 + 二分（耐心排序）模型

经典 \(O(n \log n)\) LIS 解法维护一个数组： \[ f[i] = \text{长度为 } i+1 \text{ 的递增子序列的最小可能结尾} \] 并具有如下性质：

\(f\) 是严格单调递增的
对每个新元素 \(x\)，通过二分找到最小的 \(i\)，使得： \[ f[i] \ge x \]
若不存在这样的 \(i\)，则新开一层（LIS 长度增加 1）

这一过程只关心“是否存在更优结尾”，因此可以忽略具体方案数。

3. 从“长度”到“计数”的建模升级

3.1 计数为什么不能只用 `f`

若要计数，仅知道每层的最小结尾是不够的。

原因在于：

对于同一长度 \(k\)，不同结尾值的递增子序列
对后续元素的可扩展性不同
因此它们对最终答案的贡献不能被合并

3.2 分层建模（核心思想）

沿用经典 LIS 的“层”概念：

第 \(0\) 层：长度为 1
第 \(1\) 层：长度为 2
…
第 \(i\) 层：长度为 \(i+1\)

但在每一层中，不再只保存一个结尾，而是维护：

所有可能的结尾值
以及它们对应的 方案数分布

4. 数据结构设计

4.1 `f` —— 经典 LIS 的骨架（层二分）

1	vector<int> f;

含义：

f[i]：第 \(i\) 层（长度 \(i+1\)）的最小结尾
用于在层维度上做二分，决定当前元素落在哪一层

这是对经典 LIS 的直接继承。

4.2 `d[i]` —— 每一层的“结尾值分布”

1	vector<vector<int>> d;

定义：

d[i] 保存所有“长度为 \(i+1\)”的递增子序列的结尾值
按出现顺序追加
整体单调不增

单调性来源于层的选择规则：

一个新值 \(x\) 进入第 \(i\) 层时，必然满足： \[ d[i].back() \ge x \]

4.3 `pre[i]` —— 方案数前缀和（关键设计）

1	vector<vector<int>> pre;

这是计数问题的核心。

定义方式（非常关键）：

\[ \text{pre}[i][0] = 0 \]

也就是说：

pre[i] 比 d[i] 多一个元素
pre[i][t] 表示前 \(t\) 个结尾的方案数总和

哨兵 `0` 的作用

统一区间求和公式
避免 idx-1、空区间等边界特判
使“后缀和”自然表示为： \[ \text{pre}[i].back() - \text{pre}[i][k] \]

5. 二分设计的两层结构

5.1 层二分（经典 LIS）

1 2	auto it = lower_bound(f.begin(), f.end(), x); int pos = it - f.begin();

语义：

找最小的 pos，使得 f[pos] >= x
决定 x 作为结尾时能形成的 LIS 长度为 pos + 1

5.2 层内二分（计数的关键）

在上一层 d[pos-1] 中，需要统计：

所有 结尾 < x 的序列方案数之和

由于 d[pos-1] 单调不增，可二分查找：

1	int idx = find(d[pos - 1], x);

该 idx 满足：

d[pos-1][idx ... end) 全部 < x
可接在 x 前

于是方案数为： \[ c = \text{pre}[pos-1].back() - \text{pre}[pos-1][idx] \]

6. 算法整体流程（抽象描述）

对序列从左到右遍历每个元素 \(x\)：

通过 f 二分确定层号 pos
若 pos > 0，在 d[pos-1] 中统计所有结尾 < x 的方案数
得到当前结尾的方案数 c
将 (x, c) 加入第 pos 层的数据结构
同时维护 f[pos] 的最小结尾性质

最终答案即为： \[ \text{pre}[\text{最后一层}].back() \]

7. 复杂度分析

外层遍历：\(O(n)\)
层二分：\(O(\log n)\)
层内二分：\(O(\log n)\)

总时间复杂度： \[ O(n \log n) \] 空间复杂度： \[ O(n) \]

8. AC代码

class Solution {
public:
    // 在单调不增数组 arr 中，查找第一个 < x 的位置
    // 返回的 idx 满足：
    //   arr[idx ... end) < x
    int find(vector<int>& arr, int x) {
        int l = 0, r = arr.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (arr[mid] < x)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }

    int findNumberOfLIS(vector<int>& nums) {
        vector<int> f;                   // f[i]: 第 i 层的最小结尾（LIS 骨架）
        vector<vector<int>> d;           // d[i]: 第 i 层所有结尾（单调不增）
        vector<vector<int>> pre;         // pre[i]: 方案数前缀和，pre[i][0] = 0

        for (int& x : nums) {
            // 1. 层二分：决定 x 落在哪一层
            auto it = lower_bound(f.begin(), f.end(), x);
            int pos = it - f.begin();

            // 2. 计算方案数
            int c = 1;                   // pos == 0 时，单元素序列
            if (pos > 0) {
                int idx = find(d[pos - 1], x);
                // 后缀和：所有结尾 < x 的方案数之和
                c = pre[pos - 1].back() - pre[pos - 1][idx];
            }

            // 3. 更新数据结构
            if (it == f.end()) {
                // 新开一层
                f.push_back(x);
                d.push_back({x});
                pre.push_back({0, c});   // 前缀和哨兵 + 第一个方案
            } else {
                // 覆盖最小结尾，维持 LIS 性质
                *it = x;
                d[pos].push_back(x);
                pre[pos].push_back(pre[pos].back() + c);
            }
        }

        // 最后一层的方案总数
        return pre.back().back();
    }
};

考点

思路