阅读 228

爱吃香蕉的珂珂

01、题目示例

不知道为什么叫做爱吃香蕉的阿珂,难道不应该是爱吃香蕉的猴子么...或者爱吃队友的露娜么?

第875题:阿珂喜欢吃香蕉
这里总共有 N 堆香蕉,第 i 堆中有piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。 阿珂可以决定她吃香蕉的速度 K (单位:根/小时),每个小时,她将会选择一堆香蕉,从中吃掉 K 根。

如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

示例 1:

输入: piles = [3,6,7,11], H = 8
输出: 4
复制代码

示例 2:

输入: piles = [30,11,23,4,20], H = 5
输出: 30
复制代码

示例 3:

输入: piles = [30,11,23,4,20], H = 6
输出: 23
复制代码

提示:

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9
复制代码

PS:建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。


02、二分查找

十个二分九个错,该算法被形容 "思路很简单,细节是魔鬼"。第一个二分查找算法于 1946 年出现,然而第一个完全正确的二分查找算法实现直到 1962 年才出现。下面的二分查找,其实是二分查找里最简单的一个模板,在后面的文章系列里,我将逐步为大家讲解二分查找的其他变形形式。


二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。一般二分查找由以下几个术语构成:

  • 目标 Target —— 你要查找的值

  • 索引 Index —— 你要查找的当前位置

  • 左、右指示符 Left,Right —— 我们用来维持查找空间的指标

  • 中间指示符 Mid —— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引


在最简单的形式中,二分查找对具有指定左索引和右索引的连续序列进行操作。我们也称之为查找空间。二分查找维护查找空间的左、右和中间指示符,并比较查找目标;如果条件不满足或值不相等,则清除目标不可能存在的那一半,并在剩下的一半上继续查找,直到成功为止。

举例说明:比如你需要找1-100中的一个数字,你的目标是用最少的次数猜到这个数字。你每次猜测后,我会说大了或者小了。而你只需要每次猜测中间的数字,就可以将余下的数字排除一半。

不管我心里想的数字如何,你在7次之内都能猜到,这就是一个典型的二分查找。每次筛选掉一半数据,所以我们也称之为 折半查找。一般而言,对于包含n个元素的列表,用二分查找最多需要log2n步。

当然,一般题目不太可能给你一个如此现成的题型,让你上手就可以使用二分,所以我们需要思考,如何来构造一个成功的二分查找。大部分的二分查找,基本都由以下三步组成:

  • 预处理过程(大部分场景就是对未排序的集合进行排序)

  • 二分查找过程(找到合适的循环条件,每一次将查找空间一分为二)

  • 后处理过程(在剩余的空间中,找到合适的目标值)


了解了二分查找的过程,我们对二分查找进行一般实现(这里给出一个Java版本,比较正派的代码,没有用一些缩写形式)

//JAVA 
public int binarySearch(int[] array, int des) {
    int low = 0, high = array.length - 1;
    while (low <= high) { 
        int mid = low + (high - low) / 2;
        if (des == array[mid]) { 
            return mid;
        } else if (des < array[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}
复制代码

注意:上面的代码,mid 使用 low + (high - low)/2 的目的,是防止 high low 溢出内存。


为什么说是一般实现?


1、根据边界的不同(开闭区间调整),有时需要弹性调整low与high的值,以及循环的终止条件


2、根据元素是否有重复值,以及是否需要找到重复值区间,有时需要对原算法进行改进。


那上面我们说了,一般二分查找的过程分为:预处理 - 二分查找 - 后处理,上面的代码,就没有后处理的过程,因为在每一步中,你都检查了元素,如果到达末尾,也已经知道没有找到元素。


总结一下一般实现的几个条件:


  • 初始条件:left = 0, right = length-1
  • 终止:left > right
  • 向左查找:right = mid-1
  • 向右查找:left = mid +1

请大家记住这个模板原形,在后面的系列中,我们将介绍二分查找其他的模板类型。

03、题目分析

简单复习了二分查找,我们来看本题。


注意,绝大部分 「在递增递减区间中搜索目标值」 的问题,都可以转化为二分查找问题。并且,二分查找的题目,基本逃不出三种:找特定值,找大于特定值的元素(上界),找小于特定值的元素(下界)。


而根据这三种,代码又最终会转化为以下这些问题:


  • low、high 要初始化为 0、n-1 还是 0、n 又或者 1,n?

  • 循环的判定条件是 low < high 还是 low <= high?

  • if 的判定条件应该怎么写?

  • if 条件正确时,应该移动哪边的边界?

  • 更新 low 和 high 时,mid 如何处理?


处理好了上面的问题,自然就可以顺利解决问题。将上面的思想代入到本题,我们要找 “阿珂在 H 小时吃掉所有香蕉的最小速度 K”。那最笨的就是阿珂吃的特别慢,每小时只吃掉 1 根香蕉,然后我们逐渐递增阿珂吃香蕉的速度到 i,刚好满足在 H 小时可以吃掉所有香蕉,此时 i 就是我们要找的最小速度。当然,我们没有这么笨,所以可以想到使用二分的思想来进行优化。


然后就简单了,我们寻找二分查找模板中初始条件和终止条件(注意,这里的 high、low、mid 都代表的是速度):

//这里我把最小速度定义成了1,可能大家会觉得奇怪,模板里不是0吗?
//所以这里我其实是想说,算法千变万化,大家不要生搬硬套。
//从字面理解,如果定义成0,意味着阿珂会选择一个香蕉都不吃,难道阿珂傻?   
    var low = 1
    //最大的速度,当然等于吃掉最大一堆的香蕉,毕竟一小时只能吃一堆,再大也没有意义
    var high = maxArr(piles)
    //中间速度
    var mid = (low + high) / 2
复制代码

//JAVA 
public class Solution {
        public int minEatingSpeed(int[] piles, int H) {
        int maxVal = 1;
        for (int pile : piles) {
            maxVal = Math.max(maxVal, pile);
        }
        int left = 1;
        int right = maxVal;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (canEat(piles, mid, H)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean canEat(int[] piles, int speed, int H) {
        int sum = 0;
        for (int pile : piles) {
            //向上取整
            sum += Math.ceil(pile * 1.0 / speed);
        }
        return sum > H;
    }
}
复制代码

执行结果:


额外补充(昨天有人问我的问题):


  • 第一:就是不需要再对原数组进行排序了,因为我们是把这样一个问题转化为二分查找的问题,而通过 canEat,计算在 mid 速度下吃完 piles 共需要多少小时。已经将 piles 利用进去了,所以此时并不需要对 piles 排序。
  • 第二:就是昨天有人私下问我,对 (pile speed - 1)/speed 不能理解。这个其实就是向上取整的一个小技巧,相当于 Math.ceil(pile * 1.0 / speed)。

留下一个问题,假如我们的阿珂就是笨笨的,将 low 初始化成了 0,此时的循环条件应该如何写?if 条件如果成立,low 和 high 又该如何进行调整?大家可以尝试一下!(一百个人有一百个二分,不要妄图和别人写出一模一样的代码,这是没有意义的。只有自己理解了,一步步的分析问题,写出自己的代码,才是真正属于你的)


所以,今天的问题你学会了吗?评论区留下你的想法!


我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。点击即可下载

和小浩学算法