leetcode leetcode 二分查找 答案二分

爱吃香蕉的珂珂（答案二分）

LeetCode 875 题解笔记

Posted by BY on April 26, 2026
CATALOG

    原始笔记只贴了一份代码。这里把题意和”对答案二分”的通用模板补一下，代码保持原样。

    题目背景

    LeetCode 875「爱吃香蕉的珂珂」。给定 piles[i] 表示第 i 堆香蕉的数量，珂珂每小时只能挑一堆吃且最多吃 k 根（吃完不足 k 也立刻进入下一小时），要求在 h 小时内吃完所有香蕉的最小整数速度 k。

    概念解释

    • 答案二分（在值域上二分）：当解空间是一个单调函数（速度越大、所需小时越少）时，可以直接对答案取值范围做二分查找，而不是对数组下标二分。
    • 吃完时长公式：以速度 k 吃 pile 堆需要 ceil(pile / k) 小时，整体时长 T(k) = Σ ceil(piles[i] / k)。T(k) 关于 k 单调递减。
    • 最小可行解：寻找最小的 k 使 T(k) ≤ h。

    实现原理

    1. 速度的下界是 1（至少要吃），上界是 max(piles)（一小时一堆、绰绰有余）。
    2. 在 [low, high] 上二分：
      • 若 eatingSpeed(piles, mid) ≤ h，说明 mid 可行，尝试更小：high = mid - 1；
      • 否则 mid 不够快：low = mid + 1。
    3. 循环结束时 low 即为最小可行速度。原代码额外做了一次 eatingSpeed(piles, high) 的兜底校验，本质上和”返回 low“等价，这里保留原写法不动。

    时间复杂度 O(n log max(piles))：值域二分 O(log max)，每次 eatingSpeed 扫描数组 O(n)；空间复杂度 O(1)。

    备注：ceil(pile / k) 的常用整数等价写法是 (pile + k - 1) / k，原代码用的是 pile / k + (pile % k != 0) 的等价形式，逻辑一致。

    参考实现

    class Solution {
private:
    int eatingSpeed(vector<int>& piles, int h)
    {
        if(h == 0)
        {
            // return 0;
            h = 1;
        }
        int k = 0;
        for(int i = 0; i < piles.size(); ++i)
        {
            // std::cout << h << std::endl;
            if(piles[i] % h == 0)
            {
                k += piles[i]/h;
            }else
            {
                k += piles[i]/h + 1;
            }
        }

        return k;
    }
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        if(h == 0)
        {
            return -1;
        }
        int max = 0;
        for_each(piles.begin(),piles.end(),[&](auto item){
            if(max < item)
            {
                max = item;
            }
        });

        int low = 1;
        int high = max;

        while(low <= high)
        {
            int mid = low + (high - low) / 2;
            // std::cout << low << " " << high << " " << mid << std::endl;
            if(eatingSpeed(piles,mid) <= h)
            {
                if(mid == 1)
                {
                    return mid;
                }
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }

        if(eatingSpeed(piles, high) <= h)
        {
            return high;
        }
        return high + 1;

    }
};
    FEATURED TAGS
    Git Cheat Sheet Markdown Tools C++ Linker Thread Linux TCP Network GDB Debug leetcode 链表 WSL Ubuntu Windows Linux Kernel GCC Android adb Troubleshooting Profiling Sanitizer glibc MySQL Database Python curl Build ELF clang-format CMake Graphviz Performance vcpkg Protobuf 排查 速查 内存 STL 调试 性能分析 性能 读书笔记 方法论 架构 网络 Timer mbedTLS TLS 安全 负载均衡 脚本 工具 LRU 二叉树 BST 中序遍历 回溯 二分查找 优先队列 排序 旋转数组 jenkins 部署
    FRIENDS