跳至主要內容

爱吃香蕉的珂珂：二分答案模板精讲

老张2026/4/30大约 8 分钟

爱吃香蕉的珂珂：二分答案模板精讲

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 16 分钟 | 难度：⭐⭐⭐

开篇故事

说到二分查找，大多数人第一反应是"在有序数组里找目标值"。直到我遇到了这道"爱吃香蕉的珂珂"，才算真正开窍。

这道题的数组里存的是每堆香蕉的数量，问题是找一个"吃香蕉的速度"。速度不在数组里，它在一个独立的"答案空间"上——从 1 到 max(piles)。

突然意识到：二分查找的对象可以根本不是原始数据，而是"答案本身"。答案空间是有序的（速度越大，用时越短），验证函数也是单调的（速度越大，耗时越少），所以完全可以在答案空间上二分。

这就是"二分答案"模板的精髓，也是后续 875、1011、410 等一大类题目的共同解题框架。

一、题目解析

题目（LeetCode 875）： 珂珂爱吃香蕉，n 堆香蕉，第 i 堆有 piles[i] 根。警卫离开了 h 小时，珂珂可以以每小时 k 根的速度吃香蕉（每小时最多只能吃一堆，如果这堆不够 k 根，也只花一小时吃完）。请找到她能在 h 小时内吃完所有香蕉的最小速度 k（k 为正整数）。

示例：

  • piles = [3,6,7,11]，h = 8，输出：4
  • piles = [30,11,23,4,20]，h = 5，输出：30

关键洞察：

  • 吃完第 i 堆需要 ceil(piles[i] / k) 小时，等价于 (piles[i] + k - 1) / k。
  • 对于固定速度 k，总耗时 = sum(ceil(piles[i] / k))。
  • 速度 k 越大，总耗时越小，是单调递减的关系。
  • 因此，在答案空间 [1, max(piles)] 上做 lowerBound，找最小的 k 使得总耗时 <= h。

二、解法一：暴力枚举速度（O(n * max(piles))）

思路分析

从 k=1 开始，逐一检验每个速度，找到第一个使耗时 <= h 的速度。

public class Solution1 {
    public int minEatingSpeed(int[] piles, int h) {
        int maxPile = 0;
        for (int p : piles) maxPile = Math.max(maxPile, p);

        for (int k = 1; k <= maxPile; k++) {
            if (canFinish(piles, k, h)) {
                return k;
            }
        }
        return maxPile;
    }

    private boolean canFinish(int[] piles, int k, int h) {
        long hours = 0;
        for (int p : piles) {
            hours += (p + k - 1) / k;  // 向上取整
        }
        return hours <= h;
    }
}

复杂度分析

  • 时间复杂度：O(n * max(piles))。最坏情况枚举所有速度。
  • 空间复杂度：O(1)。

三、解法二：二分答案（O(n log(max(piles)))）

思路分析

答案空间 [1, max(piles)] 有序，canFinish(k) 关于 k 单调（k 越大，越可能 finish）。在答案空间上找最小的 k 使 canFinish(k) 为 true，这就是 lowerBound 的变种。

完整代码

public class Solution2 {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int p : piles) right = Math.max(right, p);

        // 在 [1, max] 上找第一个满足条件的 k
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(piles, mid, h)) {
                right = mid;  // mid 可行，答案可能更小
            } else {
                left = mid + 1;  // mid 不可行，答案在右边
            }
        }
        return left;
    }

    private boolean canFinish(int[] piles, int k, int h) {
        long hours = 0;
        for (int p : piles) {
            hours += (p + k - 1) / k;
            if (hours > h) return false;  // 提前剪枝
        }
        return true;
    }

    public static void main(String[] args) {
        Solution2 sol = new Solution2();
        System.out.println(sol.minEatingSpeed(new int[]{3, 6, 7, 11}, 8)); // 4
        System.out.println(sol.minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 5)); // 30
        System.out.println(sol.minEatingSpeed(new int[]{312884470}, 312884469)); // 2
    }
}

复杂度分析

  • 时间复杂度：O(n log(max(piles)))。二分 O(log(max)) 次，每次验证 O(n)。
  • 空间复杂度：O(1)。

四、解法三最优：通用二分答案框架 + 细节解析

二分答案模板的通用结构

所有"二分答案"类题目都符合以下框架：

  1. 确定答案空间：答案的取值范围 [lo, hi]。
  2. 确认单调性：答案越大（或越小），验证函数的结果是否单调变化。
  3. 实现验证函数 check(mid)：对给定的答案 mid，判断它是否可行（O(n) 或 O(n log n)）。
  4. 二分求最小/最大可行答案。
// 找最小可行答案（左界）
int left = lowestPossible, right = highestPossible;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (check(mid)) right = mid;  // mid 可行，答案可能更小
    else left = mid + 1;           // mid 不可行，答案一定更大
}
return left;

// 找最大可行答案（右界）
while (left < right) {
    int mid = left + (right - left + 1) / 2;  // 注意：+1 防止死循环
    if (check(mid)) left = mid;   // mid 可行，答案可能更大
    else right = mid - 1;          // mid 不可行，答案一定更小
}
return left;

注意找最大可行答案时，mid = left + (right - left + 1) / 2，这是为了防止死循环：若 left + 1 == right 且 check(left) 为 true，mid 取 left，永远不会更新，陷入死循环。加 1 后 mid 取 right，能正常推进。

Mermaid 图：二分答案模板

完整代码（含各种边界细节）

public class Solution3 {
    public int minEatingSpeed(int[] piles, int h) {
        // 答案下界：1（至少吃1根/小时）
        // 答案上界：max(piles)（最快速度：一小时吃完最大的那堆）
        int left = 1, right = getMax(piles);

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(piles, mid, h)) {
                right = mid;      // mid 可行，找更小的速度
            } else {
                left = mid + 1;   // mid 不行，速度至少 mid+1
            }
        }

        // 循环结束时 left == right，就是最小速度
        return left;
    }

    private boolean canFinish(int[] piles, int speed, int h) {
        long totalHours = 0;
        for (int pile : piles) {
            // ceil(pile / speed) 用整数除法的向上取整实现
            totalHours += (pile + speed - 1) / speed;
            // 提前剪枝：超过 h 就没必要继续算了
            if (totalHours > h) return false;
        }
        return totalHours <= h;
    }

    private int getMax(int[] piles) {
        int max = 0;
        for (int p : piles) max = Math.max(max, p);
        return max;
    }

    /**
     * 向上取整的几种等价写法（面试时能说出来加分）
     */
    public void ceilDivExample(int pile, int k) {
        int v1 = (pile + k - 1) / k;              // 方式1：加 k-1 后整除
        int v2 = (int) Math.ceil((double) pile / k); // 方式2：强转 double 后取 ceil
        long v3 = ((long) pile + k - 1) / k;      // 方式3：避免溢出版本
        System.out.println(v1 + " " + v2 + " " + v3);
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        System.out.println(sol.minEatingSpeed(new int[]{3, 6, 7, 11}, 8));       // 4
        System.out.println(sol.minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 5)); // 30
        System.out.println(sol.minEatingSpeed(new int[]{1, 1, 1, 999999999}, 10)); // 142857143
    }
}

复杂度分析

  • 时间复杂度：O(n log(max(piles)))。
    • 二分：O(log(max(piles)))，最多约 30 次（max(piles) <= 109，log₂(109) ≈ 30）
    • 每次验证：O(n)
    • 总计：O(30n) = O(n log(max(piles)))
  • 空间复杂度：O(1)。

五、举一反三：同类题与模板应用

题号题目答案空间验证函数
1011D天内送达包裹[max(w), sum(w)]能否在 D 天内送完
410分割数组的最大值[max, sum]能否分成不超过 m 组
1482制作 m 束花所需的最少天数[1, 10^9]第 day 天能否做出 m 束
1552两球之间的磁力[1, max dist]能否放 m 个球
2064分配给商店的最多商品的最小值[1, max]能否分配给 n 个商店

二分答案的识别信号：

  • 求"最小的最大值"或"最大的最小值"
  • 验证函数存在单调性（k 越大/越小，越能满足/不满足条件）
  • 暴力枚举的时间复杂度是 O(答案范围 * n)，不可接受

六、踩坑实录

坑一：向上取整写成了向下取整

把 (p + k - 1) / k 写成了 p / k，导致结果偏小。比如 piles[i] = 7，k = 3，正确耗时是 3 小时（吃了 3+3+1），但 7/3=2（向下取整），只有 2 小时，少算了一小时。别小看这个细节，它会让所有答案都偏小一个量级。

坑二：总耗时用 int 累加导致溢出

piles 最大值为 10^9，数组最多 10^4 个元素，速度最慢是 1 时，总耗时最大是 10^4 * 10^9 = 10^13，远超 int 的范围。必须用 long 累加总耗时。我第一次提交就因为这个问题 WA 了。

坑三：right 设置为 max(piles)+1 导致多循环一次

答案的上界就是 max(piles)，不需要是 max(piles)+1。因为速度超过最大堆的大小时，每堆都只需1小时，没有任何收益，答案肯定不超过 max(piles)。

坑四：错误地设置 left = 0

速度 k 必须是正整数，最小是 1。如果设 left = 0，当 mid = 0 时，除以 0 会报错。

坑五：没有提前剪枝，超时

在 canFinish 里，一旦 totalHours > h 就可以立即返回 false，不需要继续遍历。这个剪枝在 piles 很长时能显著减少常数时间，是写出高效代码的好习惯。

七、总结

"二分答案"是二分查找最重要的扩展应用之一。它的核心思想是：当"直接求答案"很难，但"验证一个候选答案是否可行"很容易时，就可以在答案空间上二分。

识别信号：

  1. 答案是一个数值，存在明确的取值范围。
  2. "答案 >= X 可行" 或 "答案 <= X 可行"，具有单调性。
  3. 验证函数 O(n) 或 O(n log n) 可实现。

满足这三点，就可以用二分答案把时间复杂度从 O(答案范围 * n) 优化到 O(n log(答案范围))。

珂珂吃香蕉这道题是最基础的二分答案模板，后续的 1011、410 等题目都是这个框架的直接变体，掌握了这道题，那些题手到擒来。

编辑此页
最近更新:
贡献者: xiaozhangge