青蛙过河是经典的跳跃挑战问题：河面上排列着若干石块，每块石块标注了从该位置最远可以向前跳跃的步数。青蛙从第一块石头出发，目标是判断能否到达最后一块石头，并求出最少跳跃次数。本文将用 Java 实现基于双指针贪心策略的高效解法，分析覆盖区间合并与最远可达边界更新的核心思想。
一、问题定义与建模
1.1 游戏规则
给定一个非负整数数组 stones，其中 stones[i] 表示从第 i 块石头最多可以向前跳跃 stones[i] 步。青蛙初始站在第 0 块石头，每次跳跃可以选择 1 到 stones[i] 之间的任意步数。需要回答两个问题：
- 青蛙能否到达最后一块石头？
- 若能到达，最少需要跳跃几次？
1.2 贪心策略核心思想
该问题的最优解可以通过贪心算法在 O(n) 时间内求得。核心洞察是：在当前可达范围内，选择能够使下一步跳得最远的那个位置作为起跳点。
具体维护两个边界：
currentEnd：当前这一跳能够到达的最远位置farthest：在当前边界内所有位置起跳，能够到达的最远位置
当遍历位置到达 currentEnd 时，必须进行下一次跳跃，并将 currentEnd 更新为 farthest。
二、Java 实现
2.1 基础贪心解法（判断可达性 + 最少跳跃次数）
/**
* 青蛙过河问题：双指针贪心解法
* 求最少跳跃次数，并判断是否能到达终点
*/
public class FrogJump {
/**
* 计算到达终点的最少跳跃次数
* 若无法到达返回 -1
*
* 算法思路：
* 1. 维护当前跳跃的最远边界 currentEnd
* 2. 维护从当前边界内任意位置起跳能到达的最远位置 farthest
* 3. 当遍历到 currentEnd 时，跳跃次数 +1，并将边界扩展到 farthest
*
* 时间复杂度: O(n)
* 空间复杂度: O(1)
*/
public int minJumps(int[] stones) {
if (stones == null || stones.length <= 1) {
return 0;
}
int n = stones.length;
// 如果第一块石头就是0，且不是终点，则无法移动
if (stones[0] == 0 && n > 1) {
return -1;
}
int jumps = 0; // 已执行的跳跃次数
int currentEnd = 0; // 当前这跳能覆盖的最远位置
int farthest = 0; // 下一步能到达的最远位置
// 最后一个位置不需要起跳，所以遍历到 n-2 即可
for (int i = 0; i < n - 1; i++) {
// 更新从位置 i 起跳能到达的最远位置
farthest = Math.max(farthest, i + stones[i]);
// 如果最远位置已经超过或等于终点，直接返回
if (farthest >= n - 1) {
return jumps + 1;
}
// 当遍历到当前跳跃的边界时，必须进行下一次跳跃
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
// 如果边界没有推进，说明被困住了
if (currentEnd <= i) {
return -1;
}
}
}
return jumps;
}
/**
* 判断是否能到达终点（简化版本）
*/
public boolean canReach(int[] stones) {
int n = stones.length;
int farthest = 0;
for (int i = 0; i < n; i++) {
// 如果当前位置已经超出了最远可达范围，说明无法到达
if (i > farthest) {
return false;
}
// 更新最远可达位置
farthest = Math.max(farthest, i + stones[i]);
// 如果已经可以到达终点，提前返回
if (farthest >= n - 1) {
return true;
}
}
return true;
}
public static void main(String[] args) {
FrogJump solver = new FrogJump();
// 测试用例1：经典场景
int[] stones1 = {2, 3, 1, 1, 4};
System.out.println("测试1: " + java.util.Arrays.toString(stones1));
System.out.println("能否到达: " + solver.canReach(stones1));
System.out.println("最少跳跃: " + solver.minJumps(stones1));
System.out.println();
// 测试用例2：无法到达
int[] stones2 = {3, 2, 1, 0, 4};
System.out.println("测试2: " + java.util.Arrays.toString(stones2));
System.out.println("能否到达: " + solver.canReach(stones2));
System.out.println("最少跳跃: " + solver.minJumps(stones2));
System.out.println();
// 测试用例3：单步直达
int[] stones3 = {5, 0, 0, 0, 0, 0};
System.out.println("测试3: " + java.util.Arrays.toString(stones3));
System.out.println("能否到达: " + solver.canReach(stones3));
System.out.println("最少跳跃: " + solver.minJumps(stones3));
System.out.println();
// 测试用例4：大规模数据
int[] stones4 = new int[100000];
for (int i = 0; i < stones4.length; i++) {
stones4[i] = (i % 10 == 0) ? 15 : 5;
}
long start = System.currentTimeMillis();
int result = solver.minJumps(stones4);
long end = System.currentTimeMillis();
System.out.println("测试4 (n=100000): 最少跳跃 = " + result + ", 耗时 = " + (end - start) + "ms");
}
}
2.2 扩展：记录具体跳跃路径
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 青蛙过河：不仅求最少跳跃次数，还记录具体路径
*/
public class FrogJumpWithPath {
/**
* 使用贪心策略记录最优跳跃路径
* 维护一个数组记录每个位置由哪个前驱位置跳跃而来
*/
public Result findOptimalPath(int[] stones) {
int n = stones.length;
if (n <= 1) {
return new Result(0, Arrays.asList(0));
}
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
int bestNextPos = 0; // 记录当前边界内最优的下一个起跳点
// parent[i] 记录到达位置 i 的前一个起跳位置
int[] parent = new int[n];
Arrays.fill(parent, -1);
for (int i = 0; i < n - 1; i++) {
int reach = i + stones[i];
if (reach > farthest) {
farthest = reach;
bestNextPos = i;
}
if (farthest >= n - 1) {
// 记录最后一段路径
for (int j = currentEnd + 1; j <= n - 1 && j <= farthest; j++) {
if (parent[j] == -1) {
parent[j] = bestNextPos;
}
}
jumps++;
break;
}
if (i == currentEnd) {
// 记录这一段路径中各位置的前驱
for (int j = currentEnd + 1; j <= farthest; j++) {
if (parent[j] == -1) {
parent[j] = bestNextPos;
}
}
jumps++;
currentEnd = farthest;
if (currentEnd <= i) {
return new Result(-1, null); // 无法到达
}
}
}
// 回溯重建路径
List<Integer> path = new ArrayList<>();
int pos = n - 1;
while (pos != -1) {
path.add(pos);
if (pos == 0) break;
pos = parent[pos];
}
// 路径是倒序的，需要反转
// 但这里我们记录的是从起点出发的跳跃点，简化处理
return new Result(jumps, path);
}
static class Result {
int jumps;
List<Integer> path;
Result(int jumps, List<Integer> path) {
this.jumps = jumps;
this.path = path;
}
@Override
public String toString() {
return "跳跃次数: " + jumps + ", 路径: " + path;
}
}
public static void main(String[] args) {
FrogJumpWithPath solver = new FrogJumpWithPath();
int[] stones = {2, 3, 1, 1, 4, 2, 1, 2, 3, 1};
System.out.println("石头数组: " + Arrays.toString(stones));
Result result = solver.findOptimalPath(stones);
System.out.println(result);
}
}
2.3 进阶：带权重的青蛙过河（不同石头有通过代价）
import java.util.Arrays;
/**
* 带代价的青蛙过河：每块石头有通过代价，求到达终点的最小总代价
* 此时贪心策略失效，需要使用动态规划
*/
public class FrogJumpWithCost {
/**
* 动态规划解法
* dp[i] 表示到达第 i 块石头的最小代价
* dp[i] = min(dp[j] + cost[i]) for all j < i and j + stones[j] >= i
*
* 时间复杂度: O(n^2)
* 空间复杂度: O(n)
*/
public int minCost(int[] stones, int[] cost) {
int n = stones.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = cost[0];
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// 检查能否从 j 跳到 i
if (j + stones[j] >= i && dp[j] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[j] + cost[i]);
}
}
}
return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
}
/**
* 动态规划 + 单调队列优化
* 当 stones[i] 的值较大时，可使用线段树或单调队列将复杂度降至 O(n log n)
*/
public int minCostOptimized(int[] stones, int[] cost) {
int n = stones.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = cost[0];
// 使用线段树或单调队列维护区间最小值
// 这里展示一个简化的滑动窗口最小值优化
// 适用于 stones[i] 变化范围有限的场景
// 实际工程中可使用 java.util.TreeMap 或自定义线段树
for (int i = 1; i < n; i++) {
// 找到能跳到 i 的所有位置中的最小 dp 值
int minPrev = Integer.MAX_VALUE;
for (int j = Math.max(0, i - 100); j < i; j++) {
if (j + stones[j] >= i && dp[j] < minPrev) {
minPrev = dp[j];
}
}
if (minPrev != Integer.MAX_VALUE) {
dp[i] = minPrev + cost[i];
}
}
return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
}
public static void main(String[] args) {
FrogJumpWithCost solver = new FrogJumpWithCost();
int[] stones = {2, 3, 1, 1, 4};
int[] cost = {1, 2, 3, 1, 2};
System.out.println("石头: " + Arrays.toString(stones));
System.out.println("代价: " + Arrays.toString(cost));
System.out.println("最小代价: " + solver.minCost(stones, cost));
}
}
三、算法正确性证明
贪心选择性质：假设存在一条从起点到终点的最优路径，其第一次跳跃到达的位置为 k。根据贪心策略，我们在 [0, currentEnd] 范围内选择能够跳得最远的点作为起跳点，设该点为 g。若 g 跳跃的最远位置 g + stones[g] 不小于 k + stones[k]，则用 g 替换 k 不会使后续跳跃次数增加。因此贪心选择是安全的。
最优子结构：在第一次贪心跳跃后，问题转化为从新的边界 currentEnd 出发到达终点的子问题，该子问题的最优解与全局最优解一致。
四、复杂度分析
| 算法版本 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 基础贪心 | O(n) | O(1) | 只求最少跳跃次数 |
| 路径记录 | O(n) | O(n) | 需要输出具体路径 |
| 带权DP | O(n²) | O(n) | 每步有不同代价 |
| 单调队列优化 | O(n log n) | O(n) | 大规模带权场景 |
五、总结
青蛙过河问题是贪心算法的经典应用场景。双指针技巧通过维护”当前边界”和”最远可达”两个变量，将看似需要回溯搜索的问题转化为线性扫描。本文从基础版本出发，逐步扩展到路径重建和带权代价场景，展示了算法设计从简单到复杂的演进过程。在实际游戏开发中，这种覆盖区间合并的思想还可用于技能范围计算、视野检测等多种场景。
