如何找到能跳过所有障碍物的最小固定跳跃长度_技术教程

给定一个正整数数组表示直线上的障碍坐标，从原点（0）向右以**固定整数步长**跳跃，要求不踩中任何障碍；求满足条件的最小跳跃长度。

在 CodeSignal Arcade 的 “Avoid Obstacles” 问题中，核心目标是：找出最小的正整数 jump，使得从位置 0 开始，每次向右跳 jump 单位（即落在 jump, 2×jump, 3×jump, …），所有落点均不在障碍数组中。

你的原始解法逻辑基本正确：对障碍数组排序后，枚举可能的跳跃长度 jump（从 2 开始），再模拟跳跃过程，用 Arrays.binarySearch() 检查每个落点是否为障碍。一旦发现某 jump 能成功跳过所有障碍（即所有 k × jump ≤ maxObstacle 均不在数组中），就返回它。

但关键漏洞在于枚举上界设置不当。你将外层循环写为：

for (int jump = 2; jump <= 1000; jump++) { ... }

这隐含假设答案不会超过 1000 —— 然而题目约束仅说明 inputArray[i] ≤ 1000，且数组长度 ≤ 1000，并未限制答案上限。反例正是题解指出的最坏情况：

输入：[1, 2, 3, ..., 1000]（连续覆盖 1 到 1000 的
所有整数）
此时，任何 jump ≤ 1000 都必然在某次跳跃中命中障碍：
- 若 jump = k（k ≤ 1000），则第一次落点 k 就是障碍；
唯一安全的跳跃是 jump = 1001：落点为 1001, 2002, 3003, ...，全部 > 1000，自然避开所有障碍。

因此，枚举上界必须至少为 max(inputArray) + 1。由于 maxObstacle ≤ 1000，最坏情况下答案为 1001，故循环应扩展至 jump

此外，还可进一步优化逻辑，避免模拟跳跃——只需验证：对当前 jump，检查所有 jump 的倍数是否都不在障碍集中。更高效的做法是将障碍转为 HashSet（O(1) 查找），并只检查 jump, 2×jump, ..., m×jump ≤ maxObstacle（其中 m = maxObstacle / jump）。但即使保持原思路，修正边界即可通过全部测试。

✅ 修正后的 Java 实现（精简可靠版）：

import java.util.*;

int solution(int[] inputArray) {
    Arrays.sort(inputArray);
    int max = inputArray[inputArray.length - 1];

    // 枚举跳跃长度：从1开始（注意：jump=1一定失败，但逻辑需覆盖；实际可从2起，但上界必须≥max+1）
    for (int jump = 1; jump <= max + 1; jump++) {
        boolean valid = true;
        // 检查所有可能落点：jump, 2*jump, 3*jump, ... ≤ max
        for (int pos = jump; pos <= max; pos += jump) {
            // 使用二分查找判断pos是否为障碍（因已排序）
            if (Arrays.binarySearch(inputArray, pos) >= 0) {
                valid = false;
                break;
            }
        }
        if (valid) return jump;
    }
    return max + 1; // 理论上不会执行到这里，但保证返回值
}

⚠️ 注意事项：