2407. 最长递增子序列 II

发表于 分类于 阅读次数： Waline： 本文字数： 999 阅读时长 ≈ 3 分钟

考点

  • LIS
  • 线段树

思路

从暴力 DP 到值域线段树优化

1. 问题描述

给定一个整数数组 nums 和一个整数 k，要求求出一个严格递增子序列的最大长度，并满足相邻元素差值约束： \[ 0 < nums[i] - nums[j] \le k,\quad j < i \]

2. 暴力动态规划解法

2.1 状态定义

定义状态： \[ f[i] = \text{以 } nums[i] \text{ 结尾的最长合法递增子序列长度} \]

2.2 状态转移

枚举前一个位置 \(j < i\)，若满足： \[ 0 < nums[i] - nums[j] \le k \] 则可以从 \(j\) 转移到 \(i\)： \[ f[i] = \max(f[i], f[j] + 1) \] 最终答案为： \[ \max_{1 \le i \le n} f[i] \]

2.3 暴力 DP 代码（\(O(n^2)\)）

下面代码直接实现了上述转移逻辑：

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

2.4 复杂度分析

  • 时间复杂度： \[ O(n^2) \]

  • 当 \(n \le 10^5\) 时必然超时

3. 转移形式的等价变换

将转移条件按“值域”重写： \[ f[i] = 1 + \max \{ f[j] \mid nums[j] \in [nums[i]-k,\ nums[i]-1] \} \] 关键观察：

  • 转移与 下标顺序无关
  • 只关心 值域区间内的最大 DP 值

这意味着可以将“枚举所有 \(j\)”转化为：

在值域区间 \([x-k, x-1]\) 内查询最大值

4. 值域线段树建模

4.1 维护对象

定义： \[ dp[v] = \max\{\text{所有以数值 } v \text{ 结尾的子序列长度}\} \] 线段树节点维护：

  • 区间内所有 \(dp[v]\) 的最大值

4.2 操作定义

对于每个元素 \(x = nums[i]\)：

  1. 区间查询 \[ best = \max dp[v],\quad v \in [x-k, x-1] \]

  2. 单点更新 \[ dp[x] = \max(dp[x], best + 1) \]

5. 动态开点线段树实现

5.1 设计要点

  • 使用节点池，避免 new
  • 空节点表示该区间的 DP 全为 0
  • 只在访问子节点时才创建（动态开点）

节点结构：

1
2
3
4
struct node {
    int lc, rc; // 左右孩子
    int mx;     // 区间最大 dp
};

6. 线段树优化后的 AC 代码（\(O(n \log V)\)）

下面是基于上述建模的 完整 AC 实现，严格对应前面的数学推导：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
    static const int maxn = 1e5 + 5;
    int tot = 0;
    struct node {
        int lc, rc, mx;
    } t[maxn * 20];

    inline int& lc(int p) { return t[p].lc; }
    inline int& rc(int p) { return t[p].rc; }
    inline int& mx(int p) { return t[p].mx; }

    int build() {
        ++tot;
        lc(tot) = rc(tot) = mx(tot) = 0;
        return tot;
    }

    void up(int p) {
        int lmx = lc(p) == 0 ? 0 : mx(lc(p));
        int rmx = rc(p) == 0 ? 0 : mx(rc(p));
        mx(p) = max(lmx, rmx);
    }

    void add(int p, int l, int r, int pos, int v) {
        if (l == r) {
            mx(p) = max(mx(p), v);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            if (lc(p) == 0)
                lc(p) = build();
            add(lc(p), l, mid, pos, v);
        } else {
            if (rc(p) == 0)
                rc(p) = build();
            add(rc(p), mid + 1, r, pos, v);
        }
        up(p);
    }

    int ask(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return mx(p);
        int mid = (l + r) >> 1, res = 0;
        if (ql <= mid && lc(p) != 0)
            res = ask(lc(p), l, mid, ql, qr);
        if (qr > mid && rc(p) != 0)
            res = max(res, ask(rc(p), mid + 1, r, ql, qr));
        return res;
    }

    int lengthOfLIS(vector<int>& nums, int k) {
        int rt = build(), ans = 1;
        int l = INT_MAX >> 1, r = INT_MIN >> 1;
        for (int& x : nums)
            r = max(r, x), l = min(l, x - k);

        for (int& x : nums) {
            int y = ask(rt, l, r, x - k, x - 1);
            ans = max(ans, y + 1);
            add(rt, l, r, x, y + 1);
        }
        return ans;
    }
};

7. 复杂度对比总结

方法 时间复杂度 核心瓶颈
暴力 DP \(O(n^2)\) 枚举所有前驱
线段树优化 \(O(n \log V)\) 区间最大值查询

其中 \(V\) 为值域大小。

8. 总结

  • 本题的核心在于： 将“枚举前驱下标”转化为“值域区间最大值查询”
  • 动态规划转移式直接导出了线段树建模
  • 动态开点线段树使算法在大值域下仍然可行
  • 这是一个典型的 DP + 数据结构优化 题目范例