类LeetCode跳跃游戏II问题：求满足逆序最小索引规则的最优路径及高效解法

问题概述 #

这是LeetCode Jump Game II的变种问题，核心需求包括：

• 计算从起点到终点的最小步数
• 同时输出满足规则的获胜路径：不存在步数相同的其他路径，使得从路径末尾开始的任意位置索引更小（规则需从右向左应用）
• 每个位置的最大跳跃距离范围为 0 ≤ x ≤ 2^32-1，单步代价不固定为1

示例说明 #

正向场景：

• 获胜路径：[0,2,4,5,7]
• 非获胜路径：[0,1,4,6,7] → 原因：路径倒数第2个位置（索引3）的6 > 5，存在同步数但该位置索引更小的路径

反向场景：

• 获胜路径：[7,6,3,1,0]
• 非获胜路径：[7,5,4,2,0] → 原因：路径倒数第2个位置（索引3）的2 > 1，存在同步数但该位置索引更小的路径

高效解法思路 #

无需生成所有路径再筛选，核心是先计算最小步数，再反向推导唯一符合规则的路径：

1. 用贪心算法计算每个位置到终点的最小步数，时间复杂度O(n)
2. 从终点反向遍历，每一步选择当前步数下索引最小且能跳到下一个节点的位置，直接构造获胜路径

步骤详解 #

1. 计算最小步数数组

用贪心策略反向遍历，记录每个位置到终点的最小步数：

• 初始化终点步数为0
• 从右向左遍历每个位置i，若i能跳到当前已知的最小步数最远位置，则steps[i] = 该位置步数 + 1，并更新最小步数的最远位置
• 该优化将时间复杂度从O(n²)降到O(n)

2. 反向构造获胜路径

• 从终点开始，将其加入路径
• 按步数从高到低（从起点的步数-1开始递减），遍历找到最左边的位置i：
  • steps[i]等于当前目标步数
  • i的跳跃范围包含路径的第一个节点（即当前已选的前一个位置）
• 将i插入路径开头，重复直到起点

代码实现（Python） #

def find_winning_path(nums):
    n = len(nums)
    if n == 1:
        return [0]
    
    # 第一步：贪心计算每个位置到终点的最小步数
    steps = [float('inf')] * n
    steps[-1] = 0
    min_step_pos = n - 1
    for i in range(n-2, -1, -1):
        if i + nums[i] >= min_step_pos:
            steps[i] = steps[min_step_pos] + 1
            min_step_pos = i
    
    # 第二步：反向构造获胜路径
    path = [n-1]
    current_step = steps[0] - 1
    current_pos = n-1
    while current_step >= 0:
        # 找最左边的符合条件的节点
        for i in range(n):
            if steps[i] == current_step and i + nums[i] >= current_pos:
                path.insert(0, i)
                current_pos = i
                current_step -= 1
                break
    return path

# 反向场景适配：反转数组处理后再转换回原索引
def find_reverse_winning_path(nums):
    reversed_nums = nums[::-1]
    reversed_path = find_winning_path(reversed_nums)
    return [len(nums)-1 - idx for idx in reversed_path]

进一步优化 #

反向构造路径时，可以提前按步数分组存储节点（按索引升序排列），这样无需每次遍历整个数组，能进一步降低路径构造的时间开销。

内容的提问来源于stack exchange，提问作者kaixi