每日算法 — 使用java实现青蛙过河：ST表区间最小值与二分答案可行性判定

问题比看起来复杂

青蛙过河有一长串变体，其中最有算法价值的是”带高度限制的过河”：河面有 n 块石头，第 i 块石头的最大承载高度是 h[i]。青蛙从岸边（位置 0）出发，每次可以跳不超过 k 的距离，且落在石头上时，青蛙的累积体重不能超过该石头的承载上限。问：青蛙能否到达对岸（位置 n+1）？

这个问题的朴素想法是 BFS/DFS 逐格扩展——每次都试所有跳跃距离。复杂度 O(n·k)，对 n=10^5, k=10^5 就是 10^10 次操作，直接超时。

真正优雅的解法是把问题转化成”可行性判定 + 二分答案”，配合 ST 表（Sparse Table）做区间最小值查询，把复杂度压到 O(n log n)。这不是技巧堆砌，而是一个重要的思维范式：当”能否到达”这种布尔问题难以直接求值时，往往可以改造成”是否满足某个单调条件”。

一、先把状态定义清楚

设 f[i] 表示”青蛙能跳到石头 i 时，所能保留的最大剩余体力”（或者更直观地说，到达 i 之后的总体重上限余量）。状态转移：

f[i] = max{ f[j] : j < i, i - j <= k, f[j] > 0 } 然后 与 h[i] 取 min

这个递推有个麻烦：j 的范围是 [i-k, i-1]，每步都要在窗口内找最大值。窗口滑动 + 查询最大值，这是单调队列的经典场景，复杂度 O(n)。

但本文要讲的是另一种更通用的思路，因为它能处理更一般的”代价函数”。

二、二分答案 + 可行性判定

观察：如果青蛙在”每次跳跃消耗 1 点体力、落地石头的承载上限为 h[i]”的模型下能过河，那么把体力消耗改成”每次消耗 c”后，c 越小越容易过河。这是一个单调性：

消耗越小，越可能成功。

于是可以对”允许的最小剩余体力阈值”做二分，每次二分只需要判定”在给定阈值下能否过河”，判定过程是 O(n log n) 的 ST 表区间查询。

/** 判定：所有落点石头承载上限 >= need 时，青蛙能否从 0 跳到 n+1 */
static boolean feasible(int[] h, int k, int need) {
    int n = h.length;
    // 若起始位置与某石头距离 <= k 且该石头高度 >= need，则该石头可作为首个落点
    // 用 ST 表查询任意区间内的最小高度，快速判断"该区间是否存在满足高度的石头"
    ...
}

不过在这个问题里，二分答案的价值不如在”最小跳跃次数/最小代价”类问题上明显。我们先看更直接、也更通用的 ST 表版本：查询窗口内最大可达性。

三、ST 表：O(1) 区间最值

ST 表（Sparse Table）用倍增预处理，把”静态数组的任意区间最值”查询降到 O(1)。相比线段树，它不支持修改，但常数极小、代码短。

public final class SparseTable {
    private final int[][] max;    // max[k][i] = 区间 [i, i+2^k-1] 的最大值
    private final int[][] min;
    private final int[] log2;

    public SparseTable(int[] a) {
        int n = a.length;
        int K = 32 - Integer.numberOfLeadingZeros(Math.max(1, n));   // floor(log2(n)) + 1
        max = new int[K][n];
        min = new int[K][n];
        log2 = new int[n + 1];
        for (int i = 2; i <= n; i++) log2[i] = log2[i >> 1] + 1;

        for (int i = 0; i < n; i++) { max[0][i] = a[i]; min[0][i] = a[i]; }
        for (int k = 1; k < K; k++)
            for (int i = 0; i + (1 << k) <= n; i++) {
                max[k][i] = Math.max(max[k - 1][i], max[k - 1][i + (1 << (k - 1))]);
                min[k][i] = Math.min(min[k - 1][i], min[k - 1][i + (1 << (k - 1))]);
            }
    }

    /** 闭区间 [l, r] 的最大值，l <= r */
    public int queryMax(int l, int r) {
        int k = log2[r - l + 1];
        return Math.max(max[k][l], max[k][r - (1 << k) + 1]);
    }

    public int queryMin(int l, int r) {
        int k = log2[r - l + 1];
        return Math.min(min[k][l], min[k][r - (1 << k) + 1]);
    }
}

关键点：区间长度不一定是 2 的幂，所以用两段可以重叠的 2^k 区间覆盖——重叠不影响最值结果（max/min 都是幂等运算）。这一点是 ST 表能 O(1) 查询的核心，也是它和线段树（必须精确划分）的根本区别。

四、把过河判定写成 DP + ST 表

真正需要区间查询的是”青蛙在窗口 [i-k, i-1] 内能达到的最大余量”。但 DP 值随索引更新，ST 表不支持修改——所以这里要用单调队列，O(n) 完成：

/**
 * f[i] = 到达石头 i 后可用的最大承载余量（h[i] - 累计体重消耗）
 * 返回是否能到达对岸
 */
static boolean canCross(int[] h, int k, int startWeight) {
    int n = h.length;
    int[] f = new int[n + 2];
    Arrays.fill(f, -1);
    Deque<Integer> dq = new ArrayDeque<>();    // 单调递减队列，存下标

    // 起点：位置 0，视为"无限承载"
    f[0] = Integer.MAX_VALUE / 2;
    dq.addLast(0);

    for (int i = 1; i <= n + 1; i++) {
        // 弹出窗口外的下标：i - j <= k
        while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();

        if (dq.isEmpty()) return false;                 // 断崖，跳不过去
        int best = f[dq.peekFirst()];                   // 窗口内最大余量
        if (best <= 0) return false;

        int cap = (i <= n) ? h[i - 1] : Integer.MAX_VALUE / 2;   // 对岸无高度限制
        f[i] = Math.min(best - 1, cap);                 // 每次跳跃消耗 1 点承载余量
        if (i == n + 1) return f[i] > 0;                // 到达对岸且有余量

        while (!dq.isEmpty() && f[dq.peekLast()] <= f[i]) dq.pollLast();
        dq.addLast(i);
    }
    return f[n + 1] > 0;
}

为什么单调队列优于 ST 表在这里：ST 表的前提是数组静态。这里的 f[i] 是边算边填的，用不了。但窗口 [i-k, i-1] 恰好是”滑动窗口 + 求窗口内最大值”，这是单调队列的标准应用题，O(n) 且常数极小。

那 ST 表用在哪里？用在另一种变体：当石头高度是静态给定的，而我们需要反复查询”区间内有没有足够高的石头”时（例如判定”这一段河里所有石头都低于阈值 → 这段必须一次跳过去”**）。这时 ST 表就派上用场：

/** 在 [l, r] 内查找第一个高度 >= need 的石头位置，找不到返回 -1 */
static int firstAtLeast(SparseTable st, int[] h, int l, int r, int need) {
    // 二分 + ST 表查询，O(log n)
    int lo = l, hi = r, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (st.queryMax(l, mid) >= need) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

这里 ST 表 + 二分的组合把”找第一个满足条件的位置”从 O(n) 降到 O(log n)。当需要在一局中做大量这类查询时（比如路径规划中的多候选评估），总复杂度从 O(n²) 降到 O(n log n)。

五、二分答案用在”最少跳跃次数”

另一个高频变体：给定最大跳跃距离 k，求最少跳几次能过河（青蛙可以在同一位置停留，也可以跳过石头）。这个问题可以二分”跳跃次数 m“，判定”跳 m 次能否到达 n+1“。

判定用贪心：要覆盖 [0, n+1] 这段距离，每次最多跳 k。若只要求”能到对岸、不受石头高度限制”，答案是 ceil((n+1)/k)——太平凡。但加上”必须落在石头上”的约束后，问题变成区间覆盖：

/** 二分跳跃次数 m，判定能否用 m 次跳跃从 0 到达 n+1，每跳 <= k，且中间落点必须是石头 */
static boolean canReachInMSteps(int[] h, int k, int m) {
    int n = h.length, pos = 0;
    int[] reach = new int[n + 2];       // reach[i] = 跳到 i 所需的最少次数
    Arrays.fill(reach, Integer.MAX_VALUE);
    reach[0] = 0;
    for (int i = 1; i <= n + 1; i++) {
        int best = Integer.MAX_VALUE;
        for (int j = Math.max(0, i - k); j < i; j++) {
            if (reach[j] != Integer.MAX_VALUE) best = Math.min(best, reach[j] + 1);
        }
        if (i <= n && h[i - 1] < 0) continue;        // 该石头不可用（例如已破损）
        reach[i] = best;
    }
    return reach[n + 1] <= m;
}

上面的内层循环是 O(k)，总 O(nk)。改成单调队列后：

static int minSteps(int[] h, int k) {
    int n = h.length;
    int[] dp = new int[n + 2];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    Deque<Integer> dq = new ArrayDeque<>();
    dq.addLast(0);
    for (int i = 1; i <= n + 1; i++) {
        while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();
        if (dq.isEmpty()) return Integer.MAX_VALUE;         // 无法到达
        dp[i] = dp[dq.peekFirst()] + 1;
        if (i <= n && h[i - 1] < 0) continue;              // 破损石头不能落脚
        while (!dq.isEmpty() && dp[dq.peekLast()] >= dp[i]) dq.pollLast();
        dq.addLast(i);
    }
    return dp[n + 1];
}

注意这里队列维护的是最小值的单调队列：队首是窗口内 dp 最小的下标。因为 dp[i] 都是单调递增的（跳得越远次数不会更少），所以队列实际上一直只有队首在起作用——但代码的通用性保留了”dp 非单调”的变体（如带权跳跃）。

六、完整工程结构

frog-crossing/
├── pom.xml
└── src/main/java/frog/
    ├── SparseTable.java   // 倍增预处理 + O(1) 区间最值
    ├── CrossSolver.java   // 单调队列 DP：最大余量 / 最少步数
    ├── BinarySearch.java  // 二分答案框架 + 单调性判定
    └── Main.java          // 三种变体的调用示例

Main：

public static void main(String[] args) {
    int[] h = {3, 5, 2, 6, 4, 1, 7};      // 7 块石头的承载上限
    int k = 3;                              // 最大跳跃距离
    System.out.println("能否过河: " + CrossSolver.canCross(h, k, 8));
    System.out.println("最少跳数: " + CrossSolver.minSteps(h, k));

    int[] heights = {3, 5, 2, 6, 4, 1, 7};
    SparseTable st = new SparseTable(heights);
    System.out.println("区间[1,4]最大高度: " + st.queryMax(1, 4));
    System.out.println("区间[0,3]第一个>=5的位置: "
        + CrossSolver.firstAtLeast(st, heights, 0, 3, 5));
}

七、复杂度与三种解法的取舍

最重要的判断原则：数据是否静态。石头高度不会变 → ST 表可用；f[i] 边算边变 → 只能用单调队列或线段树。

八、从这道题能带走的方法论

第一，滑动窗口最值先想单调队列。 只要”窗口大小固定、求窗口内最值”，单调队列几乎总是最优解，O(n) 且无需平衡树。它的本质是”及时删除永远不会再成为答案的候选”。

第二，区间最值先想 ST 表。 静态数组 + 大量查询 + 不需要修改，这就是 ST 表的设计目标。O(1) 查询的秘诀是”用两段可重叠的 2^k 区间覆盖”，重叠对 max/min 无害。

第三，看到”能否”就想想能不能二分。 布尔判定问题如果有单调性（参数越大越容易满足），二分就是免费的加速器。反过来，如果”能否”没有单调结构，二分毫无意义——这一步判断错了，后面全是无用功。

第四，别把”最优解”和”可行解”混淆。 青蛙过河问的是”能否到达”，而最少步数问的是”最少几次”。前者单调队列一次扫描即可，后者才需要 DP 递推。很多实现把两者混在一起，既慢又难验证。

这三种工具在路径规划、滑动窗口统计、资源调度里出现的频率极高。青蛙过河只是把它们放进了一个有画面感的外壳——跳石头这个动作，恰好就是”状态转移”的物理投影。