数组跳跃序列长度

题目描述

给定长度为 n 的数组 a 和整数 d。对于每个起点 i，从当前位置不断寻找最小的下标 j > i 满足：

$$a_j \ge a_i + d$$

找到后跳到 j，令 i = j 继续；找不到则停止。

输出从每个下标出发能经过的下标序列长度。

输入格式：

• 第一行 t，测试用例数量；
• 每个测试用例：第一行 n, d，第二行长度为 n 的数组 a。

输出格式：每个测试用例输出一行，共 n 个整数，表示从每个下标出发的跳跃序列长度。

示例

输入：
1
5 3
1 4 2 5 8

从 i = 0 出发：a[0] = 1，需要最小的 j > 0 满足 a[j] >= 4，即 j = 1；从 j = 1 出发需要最小的 j' > 1 满足 a[j'] >= 7，即 j' = 4；从 j = 4 出发找不到，停止。序列长度 3。

从 i = 1 出发：需要 a[j] >= 7，j = 4，长度 2。

从 i = 2 出发：需要 a[j] >= 5，j = 3；从 j = 3 出发需要 a[j'] >= 8，j' = 4，长度 3。

从 i = 3 出发：需要 a[j] >= 8，j = 4，长度 2。

从 i = 4 出发：找不到，长度 1。

输出：
3 2 3 2 1

核心思路

DP 定义

定义 dp[i] 表示「从下标 i 出发能经过的下标序列长度」。

• 若存在最小的合法 j > i（a_j >= a_i + d），则 dp[i] = dp[j] + 1；
• 若不存在，则 dp[i] = 1。

因为 j > i，所以 dp[j] 已经在「从右往左」的处理顺序下计算好了。

关键难点：如何快速找到「最小的 j > i 满足 a_j >= a_i + d」。

朴素做法

从右往左计算 dp，对每个 i，从 i + 1 开始线性扫描，找第一个 a_j >= a_i + d 的 j。

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

n 较大时会超时。

单调栈 + 二分

核心观察：如果 j1 < j2 且 a_{j1} >= a_{j2}，那么 j2 永远不会成为答案——因为任何 j2 能满足的条件 a_{j2} >= target，j1 都满足，且 j1 更小。j2 被 j1 支配。

利用这个性质，可以维护一个不被支配的候选下标栈，栈内元素满足：

• 下标从栈底到栈顶递减；
• 对应的 a 值从栈底到栈顶严格递减。

处理过程：从右往左遍历 i：

1. 在栈中二分查找：找满足 a[stack[k]] >= a_i + d 的最靠栈顶的位置 k（对应最小的下标 j）；
2. 若找到，dp[i] = dp[stack[k]] + 1；
3. 否则 dp[i] = 1；
4. 弹栈：弹出所有 a[stack[-1]] <= a[i] 的栈顶元素（它们被 i 支配）；
5. 把 i 入栈。

为什么二分成立：栈内 a 值从栈底到栈顶递减，是单调序列，可以二分。

为什么先查询后弹栈：弹栈前的栈包含所有 j > i 的未支配元素，才是查询的合法候选集；弹栈是为了给后续更左侧的 i 维护候选集，不影响当前查询。

示例走一遍

a = [1, 4, 2, 5, 8]，d = 3，从右往左：

i	a[i]	target	查询时栈	二分找到的 k	dp[i]	弹栈后	入栈后
4	8	11	[]	无	1	[]	[4]
3	5	8	[4]	k=0	2	[4]	[4, 3]
2	2	5	[4, 3]	k=1	3	[4, 3]	[4, 3, 2]
1	4	7	[4, 3, 2]	k=0	2	[4, 3]	[4, 3, 1]
0	1	4	[4, 3, 1]	k=2	3	[4, 3, 1]	[4, 3, 1, 0]

dp = [3, 2, 3, 2, 1]，正确。

参考代码

单调栈 + 二分（$O(n \log n)$）

t = int(input())
for _ in range(t):
    n, d = map(int, input().split())
    arr = list(map(int, input().split()))

    dp = [1] * n
    stack = []      # 存下标，从栈底到栈顶：下标递减，值递减

    for i in range(n - 1, -1, -1):
        target = arr[i] + d

        # 二分：找满足 arr[stack[k]] >= target 的最靠栈顶位置（即最小下标 j）
        lo, hi = 0, len(stack) - 1
        k = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if arr[stack[mid]] >= target:
                k = mid
                lo = mid + 1        # 往栈顶方向找
            else:
                hi = mid - 1

        if k != -1:
            dp[i] = dp[stack[k]] + 1

        # 弹栈：弹出所有被 i 支配的栈顶元素
        while stack and arr[stack[-1]] <= arr[i]:
            stack.pop()

        stack.append(i)

    print(' '.join(map(str, dp)))

暴力做法（$O(n^2)$）

t = int(input())
for _ in range(t):
    n, d = map(int, input().split())
    arr = list(map(int, input().split()))

    ans = []
    for i in range(n):
        length = 1
        cur = arr[i]
        for j in range(i + 1, n):
            if cur + d <= arr[j]:
                cur = arr[j]
                length += 1
        ans.append(length)

    print(' '.join(map(str, ans)))

复杂度分析

方法	时间	空间	特点
暴力	$O(n^2)$	$O(n)$	思路直接，适合小数据
单调栈 + 二分	$O(n \log n)$	$O(n)$	大数据首选

• 单调栈 + 二分：每个下标最多入栈、出栈一次，共 $O(n)$ 次栈操作；每次二分 $O(\log n)$，总时间 $O(n \log n)$。
• 空间：dp 数组 $O(n)$，栈 $O(n)$。

关键细节

1. 为什么用「不被支配」的栈

若 j1 < j2 且 a_{j1} >= a_{j2}，则 j2 被 j1 支配。任何 j2 能作为答案的场景，j1 也能，且 j1 更小（更优）。

所以被支配的下标永远不会成为答案，弹掉它们不影响正确性，反而缩小了查询范围。

2. 栈内为什么 a 值严格递减

每次推入 i 之前，弹出所有 a[stack[-1]] <= a[i] 的栈顶。所以剩下的栈内元素都满足 a[stack[j]] > a[i]，保持严格递减。

3. 二分为什么找「最靠栈顶」的位置

要找最小的下标 j > i，而栈内下标从栈底到栈顶递减，栈顶对应最小下标。所以找「满足 a[stack[k]] >= target 的最靠栈顶位置」即最小合法下标。

4. 为什么先查询后弹栈

查询时栈中应包含所有 j > i 的未支配元素，这是查询的合法候选集。弹栈是为了给后续更左侧的 i 维护正确的候选集，不影响当前查询。

5. dp[i] = dp[stack[k]] + 1 的含义

找到最小的合法 j 后，直接跳到 j，之后的最长序列长度就是 dp[j]，加上当前这一步。

6. 与经典 LIS 的区别

• LIS：求最长递增子序列长度，不要求「最小跳跃目标」；
• 本题：每步必须跳到「最小的合法 j」，是确定性的跳跃过程，不是最优选择。

所以本题更接近「模拟 + 加速查询」的问题，而不是 LIS 那种「取最优」的 DP。

总结

• 问题转化：dp[i] = dp[j] + 1，其中 j 是最小的 j > i 满足 a_j >= a_i + d；
• 核心挑战：如何快速找这个 j；
• 支配关系：若 j1 < j2 且 a_{j1} >= a_{j2}，则 j2 永远不会成为答案，可删除；
• 单调栈：维护不被支配的候选，栈内 a 值严格递减；
• 二分：在递减序列中找「满足 a >= target 的最靠栈顶位置」，即最小合法下标；
• 时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

相关题目

• LC 300. 最长递增子序列（LIS，二分 + 贪心）
• LC 1438. 绝对差不超过限制的最长连续子数组（单调队列 + 滑动窗口）
• LC 239. 滑动窗口最大值（单调队列）
• 单调栈专题：LC 739、LC 84、LC 42