每日算法 — 使用java实现青蛙过河：单调队列优化DP与双端滑窗

可莉爸爸 AI算法

一、游戏场景：青蛙过河的两种经典玩法

“青蛙过河”在两个方向上都是算法经典：

  1. 变体 A（最少跳跃数）：一排石头，青蛙从岸边出发，每跳不超过 L，问最少几跳能到对岸；
  2. 变体 B（最收益路径）：青蛙每跳的距离必须落在 [D, D+K] 之间（太近跳不过去、太远跳不动），每块石头有一个”通过代价/价值”，问走哪条路线收益最大。

变体 A 是贪心 + 双指针的教科书例子；变体 B 是一个典型的滑窗 DP：

dp[i] = value[i] + max{ dp[j] : D ≤ pos[i] - pos[j] ≤ D + K }

这个递推式里的 max 只在”一个随 i 右移的窗口”内取值，因此可以用单调队列把每次转移从 O(n) 压到摊还 O(1)，整体从 O(n²) 降到 O(n)。本文把两种变体都实现一遍，重点讲变体 B 里最容易被写错的那个细节：窗口的上下界是两个方向不同的约束。

二、为什么必须是”窗口”而不是”前缀”

很多跳跃类 DP 的题解会写成 max{ dp[j] : j < i }，这在青蛙过河里是错的，原因有两层：

  1. 下界约束：pos[i] - pos[j] ≥ D 意味着”离得太近的石头跳不过去”，所以不是所有 j < i 都合法，最近的几块反而不能用；
  2. 上界约束：pos[i] - pos[j] ≤ D + K 意味着”离得太远的石头够不着”，所以更早的石头也会失效。

于是合法集合是 [lo(i), hi(i)]：

lo(i) = min{ j : pos[i] - pos[j] ≤ D + K }        （再往前就太远）
hi(i) = max{ j : pos[i] - pos[j] ≥ D }            （再往后就太近）

由于 pos 单调递增，lo(i) 与 hi(i) 都随 i 单调不减——这是能把 O(n²) 降到 O(n) 的唯一理由。如果坐标乱序，这套优化立刻失效（必须换成分块、线段树或 Li Chao 树）。

三、单调队列的机制

维护一个存”下标”的双端队列，保持两个不变量：

  • 下标递增：因为按 j 从前往后入队；
  • dp 值递减：入队时从队尾弹掉所有 dp 不大于新值的元素——它们永远不可能再成为窗口最大值。

三项操作：

  • 入队：while 队尾 dp ≤ dp[i]: 弹出队尾；然后 push_back(i)；
  • 出队（过期）：从队首弹掉已不在窗口内的下标（按坐标判定，不按下标）；
  • 取最值：队首即窗口最大值。

因为队列里下标递增，所有”过期”（下标过小）的元素必然集中在队首，所以”弹队首”就足够——但前提是过期判定必须只用”太远”这一个方向。下界”太近”如何落地，是本文第四节的重点。

package com.algodaily.frog;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.function.IntPredicate;

/**
 * 单调队列：维护滑动窗口最大值。
 * 队列存下标，比较依据是外部传入的 value 数组。
 * 不变量：队列内下标严格递增，value 严格递减。
 */
public final class MonotonicDeque {

    private final Deque<Integer> deque = new ArrayDeque<>();

    /** 入队：先把队尾所有 value <= 新值的元素弹掉，再把新下标放到队尾 */
    public void push(int index, long[] value) {
        while (!deque.isEmpty() && value[deque.peekLast()] <= value[index]) {
            deque.pollLast();
        }
        deque.addLast(index);
    }

    /** 弹出队首所有满足条件（已过期）的元素 */
    public void evictWhile(IntPredicate isExpired) {
        while (!deque.isEmpty() && isExpired.test(deque.peekFirst())) {
            deque.pollFirst();
        }
    }

    /** 窗口最大值对应的下标；空队列返回 -1 */
    public int bestIndex() { return deque.isEmpty() ? -1 : deque.peekFirst(); }

    public boolean isEmpty() { return deque.isEmpty(); }
    public int size() { return deque.size(); }
    public void clear() { deque.clear(); }
}

把”过期判定”做成 IntPredicate 回调，是为了让同一个队列类既能服务”固定宽度窗口”，也能服务”由坐标区间决定的窗口”。这是本篇里最值得记住的一处抽象。

四、变体 B 的正确实现

4.1 数据结构

package com.algodaily.frog;

/** 一块石头：坐标与价值（收益 / 踩塌代价） */
public final class Stone {
    public final long pos;
    public final long weight;

    public Stone(long pos, long weight) {
        this.pos = pos;
        this.weight = weight;
    }

    @Override
    public String toString() { return "Stone(pos=" + pos + ", w=" + weight + ")"; }
}

4.2 求解结果

package com.algodaily.frog;

/** 求解结果：最大收益、最优路径（石头下标）、是否可达 */
public final class FrogResult {

    public final long maxValue;
    public final int[] path;
    public final boolean reachable;

    public FrogResult(long maxValue, int[] path, boolean reachable) {
        this.maxValue = maxValue;
        this.path = path;
        this.reachable = reachable;
    }

    /** 路径对应的坐标序列，便于打印 */
    public long[] positions(Stone[] stones) {
        long[] out = new long[path.length];
        for (int i = 0; i < path.length; i++) out[i] = stones[path[i]].pos;
        return out;
    }
}

4.3 主算法：双指针定窗口 + 单调队列取最值

职责分离是这版实现的核心：双指针负责”哪些下标在窗口内”，单调队列只负责”窗口里谁的 dp 最大”。

package com.algodaily.frog;

import java.util.Arrays;

/**
 * 青蛙过河（变体 B）。
 *
 * 转移： dp[i] = weight[i] + max{ dp[j] : minJump <= pos[i]-pos[j] <= maxJump }
 *
 * 合法下标构成区间 [lo, hi]，且 lo、hi 都随 i 单调不减 => 双指针 O(n)。
 * 区间内取最大值用单调队列，摊还 O(1)。
 *
 * 前提： stones 按 pos 严格递增；stones[0] 是起点，stones[n-1] 是终点。
 */
public final class FrogWindowDp {

    private static final long NEG = Long.MIN_VALUE / 4;

    public static FrogResult solve(Stone[] stones, long minJump, long maxJump) {
        if (minJump > maxJump) throw new IllegalArgumentException("minJump 不能大于 maxJump");

        int n = stones.length;
        long[] dp = new long[n];
        int[] parent = new int[n];
        Arrays.fill(dp, NEG);
        Arrays.fill(parent, -1);

        dp[0] = stones[0].weight;   // 起点收益计入

        MonotonicDeque window = new MonotonicDeque();
        int lo = 0;      // 窗口左端（可能已过期，但尚未弹出）
        int hi = -1;     // 窗口右端（已入队的最大下标）

        for (int i = 1; i < n; i++) {
            long posI = stones[i].pos;

            // ① 推进右端点：把所有满足 pos[i] - pos[j] >= minJump 的 j 入队
            //    （下标递增入队，保持"队列内下标递增"不变量）
            while (hi + 1 < i && posI - stones[hi + 1].pos >= minJump) {
                hi++;
                if (dp[hi] != NEG) window.push(hi, dp);
            }

            // ② 推进左端点：把所有满足 pos[i] - pos[j] > maxJump 的 j 移出窗口
            while (lo <= hi && posI - stones[lo].pos > maxJump) {
                lo++;
            }

            // ③ 让队列与窗口同步：弹出所有下标 < lo 的队首元素
            //    由于队列内下标递增，这些元素必然都在队首连续段上
            final int lowerBound = lo;
            window.evictWhile(j -> j < lowerBound);

            if (window.isEmpty()) {
                dp[i] = NEG;        // 当前石头不可达，不入队
                continue;
            }

            int best = window.bestIndex();
            dp[i] = dp[best] + stones[i].weight;
            parent[i] = best;
        }

        int last = n - 1;
        if (dp[last] == NEG) return new FrogResult(NEG, new int[0], false);
        return new FrogResult(dp[last], restore(parent, last), true);
    }

    /** 回溯路径：从终点沿 parent 走到起点，再反转 */
    private static int[] restore(int[] parent, int end) {
        int len = 0;
        for (int k = end; k >= 0; k = parent[k]) {
            len++;
            if (parent[k] == -1) break;
        }
        int[] path = new int[len];
        int idx = len - 1;
        int k = end;
        while (idx >= 0) {
            path[idx--] = k;
            if (parent[k] == -1) break;
            k = parent[k];
        }
        return path;
    }
}

三个关键点，逐条解释：

（1）为什么先推进 hi 再推进 lo？
hi 只增不减，lo 只增不减，两个指针独立。先把右端推到位，才能保证入队的都是”够得着且跳得过去”的候选；左端随后清理”太远”的。顺序反过来的话，lo 会先越过还没入队的下标，导致数量对不上。

（2）为什么用 lo 的下标而非坐标来做弹出条件？
因为队列里存的就是下标。若用坐标判定（stones[j].pos 与阈值比较），在 pos 有重复值时会出现歧义；用下标做严格比较，语义最清晰：j < lo 就是”不在窗口内”。

（3）为什么 dp[i] == NEG 的石头不入队？
不可达的石头若进队，会让”不可达路径”以 NEG + w 的形式继续传播，最后 dp 里全是巨大的负数而不是恰好 NEG。这类 bug 不会崩溃，只会让”是否可达”的判定失效——比崩溃更难发现。

五、变体 A：最少跳跃数

package com.algodaily.frog;

import java.util.ArrayDeque;
import java.util.Arrays;

/** 青蛙过河（变体 A）：从 0 跳到 >= target，每跳不超过 maxJump，求最少跳数 */
public final class MinJump {

    /**
     * 贪心 + 双指针，O(n)。
     * reach    = 当前跳数下能到达的最远坐标
     * nextReach= 从 reach 范围内任一点再跳一次能到达的最远坐标
     * 每一跳都把"可达最远处"推到极限，因此跳数最少。
     */
    public static int greedy(long[] positions, long target, long maxJump) {
        if (target <= maxJump) return 1;

        int jumps = 0;
        long reach = 0;
        long nextReach = 0;
        int idx = 0;
        int n = positions.length;

        while (reach < target) {
            jumps++;
            // 把所有落在 (reach, reach + maxJump] 的石头作为本跳的候选落点
            while (idx < n && positions[idx] <= reach + maxJump) {
                nextReach = Math.max(nextReach, positions[idx] + maxJump);
                idx++;
            }
            if (nextReach <= reach) return -1;  // 没有新落点，卡住了
            reach = nextReach;
        }
        return jumps;
    }

    /** BFS 版本：正确性基准，便于对拍 */
    public static int bfs(long[] positions, long target, long maxJump) {
        int n = positions.length;
        long[] nodes = new long[n + 2];
        nodes[0] = 0;
        System.arraycopy(positions, 0, nodes, 1, n);
        nodes[n + 1] = target;
        int total = n + 2;

        int[] dist = new int[total];
        Arrays.fill(dist, -1);
        dist[0] = 0;

        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(0);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v = u + 1; v < total; v++) {
                if (nodes[v] - nodes[u] > maxJump) break; // 坐标递增，后面更远，直接断
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    queue.add(v);
                }
            }
        }
        return dist[total - 1];
    }
}

贪心版里还有一个细节：nextReach 跨轮次不清零是正确的（它代表”累积可达最远”），但 reach 必须在每轮用 nextReach 刷新——这两个变量混用会少算一跳，这类差一错误在跳跃问题上极常见，用 BFS 对拍是成本最低的保险。

六、演示与随机对拍

package com.algodaily.frog;

import java.util.Arrays;
import java.util.Random;

/** 入口：演示最优路径 + 对拍两套实现 */
public final class FrogApp {

    public static void main(String[] args) {
        demoMaxWeight();
        demoMinJump();
        stressMaxWeight();
    }

    private static void demoMaxWeight() {
        // 起点 0，终点 30，中间若干石头；weight 代表"通过难度/收益"
        Stone[] stones = {
                new Stone(0, 0),
                new Stone(5, 10),
                new Stone(9, 30),
                new Stone(12, 5),
                new Stone(16, 50),
                new Stone(20, 8),
                new Stone(24, 60),
                new Stone(27, 15),
                new Stone(30, 0),
        };
        FrogResult r = FrogWindowDp.solve(stones, 3, 9);
        System.out.println("可达 = " + r.reachable + "，最大收益 = " + r.maxValue);
        System.out.println("下标路径 = " + Arrays.toString(r.path));
        System.out.println("坐标路径 = " + Arrays.toString(r.positions(stones)));
    }

    private static void demoMinJump() {
        long[] pos = {5, 8, 13, 19, 24, 29};
        System.out.println("最少跳数（贪心）= " + MinJump.greedy(pos, 32, 7));
        System.out.println("最少跳数（BFS）  = " + MinJump.bfs(pos, 32, 7));
    }

    /** 对拍：单调队列版 vs 朴素 O(n²) 版 */
    private static void stressMaxWeight() {
        Random rnd = new Random(20261101L);
        int mismatch = 0;

        for (int iter = 0; iter < 500; iter++) {
            int n = 2 + rnd.nextInt(25);
            long[] pos = new long[n];
            pos[0] = 0;
            for (int i = 1; i < n; i++) pos[i] = pos[i - 1] + 1 + rnd.nextInt(6);

            Stone[] stones = new Stone[n];
            for (int i = 0; i < n; i++) {
                stones[i] = new Stone(pos[i], (i == 0 || i == n - 1) ? 0 : rnd.nextInt(50));
            }

            long minJump = 1 + rnd.nextInt(5);
            long maxJump = minJump + rnd.nextInt(10);

            long fast = FrogWindowDp.solve(stones, minJump, maxJump).maxValue;
            long slow = bruteForce(stones, minJump, maxJump);
            if (fast != slow) {
                mismatch++;
                System.out.println("不一致 iter=" + iter + " fast=" + fast + " slow=" + slow);
            }
        }
        System.out.println("对拍完成，不一致 = " + mismatch);
    }

    /** 朴素 O(n²) DP：逐对检查距离，作为正确性基准 */
    private static long bruteForce(Stone[] stones, long minJump, long maxJump) {
        int n = stones.length;
        long NEG = Long.MIN_VALUE / 4;
        long[] dp = new long[n];
        Arrays.fill(dp, NEG);
        dp[0] = stones[0].weight;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long d = stones[i].pos - stones[j].pos;
                if (d < minJump || d > maxJump) continue;
                if (dp[j] == NEG) continue;
                dp[i] = Math.max(dp[i], dp[j] + stones[i].weight);
            }
        }
        return dp[n - 1];
    }
}

七、复杂度与四个易错点

方案 时间 空间 适用
朴素 DP O(n²) O(n) n ≤ 5000 的验证 / 对拍
双指针 + 单调队列 O(n) 摊还 O(n) 坐标有序、窗口两端单调
贪心（最少跳数） O(n) O(1) 仅”每跳有上限”类问题
BFS O(n²) 最坏 O(n) 通用基准

按踩坑频率排序的四条：

  1. 窗口用下标而不是坐标定义。约束是 pos[i] - pos[j] ∈ [D, D+K]，若写成”最近 W 块石头”，在石头疏密不均时会立刻算错。
  2. 两个方向约束的处理顺序。左端（太远）对应”下标过小”，右端（太近）对应”下标过大但不大于 hi“。真正的技巧是用双指针把窗口两端都显式推到位，让单调队列只做”取最大值”这一件事——职责分离后，每一行都能单独验证。
  3. dp == NEG 不能入队。不可达状态进队会让”不可达”伪造成”可达但收益极低”，NEG 语义被污染，”是否可达”的判断直接失效。
  4. 贪心的差一错误。reach 与 nextReach 混用会少算一跳；务必用 BFS 对拍。

八、这道题真正的教学价值

青蛙过河是”窗口 DP“最干净的入口，它把三件事同时摊在你面前：

  • 状态定义：dp[i] 只依赖窗口内的 dp[j]，窗口外的历史全部作废；
  • 转移优化：取窗口最大值的 max 操作，正是单调队列存在的唯一理由；
  • 约束方向：上界（太远）与下界（太近）是两类不同方向的约束，落地方式不同。

一旦理解”窗口两端由坐标决定、两端都单调右移”这个结构，你会发现一批题目其实是同一道题：滑动窗口最大值、股票含冷冻期的买卖、限流器的令牌桶、时序数据库的滑窗聚合——它们都能被同一个单调队列模板吃掉。这才是学这道题真正划得来的地方。

Tagged with: