5.3-5.4二分搜索算法实例

5.3 如何应用二分搜索算法

5.3.1 问题分析

• 二分搜索所应用到实际的算法的问题时，通常所具有的一个特征是:搜索空间是有序的。

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/koko-eating-bananas
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 也就是输入一个长度为N的正整数数组piles代表 N堆香蕉，piles[i]第i堆香蕉的数量，现在koko要在H小时内吃完这些香蕉
• Koko吃香蕉的速度为每小时k根，而且每小时最多吃一堆香蕉，如果吃不下的话留到下一小时再吃，如果吃完了这堆还有胃口，他也只会等到下一小时才吃下一堆
• 在这个条件下，请你编写一个算法，计算Koko每小时至少要吃几根香蕉，才能在H小时内把这些香蕉吃完?
• 算法要求的是H小时内吃完香蕉的最小速率，不妨设Koko吃香蕉的速率为speed，请问speed至多可能为多少?至少可能为多少呢?

至少:至少会是1，因为如果是0的话根本不可能吃完香蕉

至多:至多会是max(piles)，因为一小时最多只能吃一堆香蕉

5.3.2 代码实现

• 暴力解法:从1枚举到max(piles),一旦发现某个值可以在H小时内吃完所有香蕉，这个就是最小速度

    public int minEatingSpeed(int[] piles, int h) {
        int max = piles[getMaxIndex(piles)];
        int speed;
        for(speed = 1;speed<=max;speed++){
            if(canFinish(piles,speed,h)){
                break;
            }
        }
        return speed;
    }
1
2
3
4
5
6
7
8
9
10

• 观察这个for循环，其特点是在连续的空间线性搜索，这就是二分搜索可以发挥作用的标志，由于要求的是最小速度，所以可以用一个搜索左侧边界的二分搜索来代替线性搜索

    public int minEatingSpeed(int[] piles, int h) {
        int left =1,right=piles[getMaxIndex(piles)]+1;//定义搜索区间[left,right),right不可达
        while (left < right){
            int mid = left + (right-left)/2;
            if(canFinish(piles,mid,h)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
1
2
3
4
5
6
7
8
9
10
11
12

• 来回顾一下为什么这样能够搜索得到左侧的边界
  • 首先咱的搜索区间是[left,right),然后当我们要找到左侧边界的时候，处理如下:当找到合理的target的时候，我们将right向左侧逼近，不断向左收缩，从而得到锁定左侧边界的效果

    public int minEatingSpeed(int[] piles, int h) {
        int left =1,right=piles[getMaxIndex(piles)]+1;//定义搜索区间[left,right),right不可达
        while (left < right){
            int mid = left + (right-left)/2;
            if(canFinish(piles,mid,h)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
    //O(N)
    private boolean canFinish(int[] piles,int speed,int h){
        int time = 0;
        for (int pile : piles) {
            time += timeOf(pile,speed);
            if(time>h){
                return false;
            }
        }
        return time<=h;
    }
    //以speed的速度吃香蕉,将要吃多久?
    private int timeOf(int n,int speed){
        //如果n>speed的时候,整数向上取整,比如说我的n是5,speed是2,需要3个小时
        //如果n
        return (n/speed)+((n%speed>0)?1:0);
    }
    private int getMaxIndex(int[] piles){
        int idx=0,max=Integer.MIN_VALUE;
        for(int i = 0;i<piles.length;i++){
            if(max<piles[i]){
                max = piles[i];
                idx = i;
            }
        }
        return idx;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

5.3.3 扩展延伸

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 这道题与上一道题是类似的。给你一个正整数数组weights和一个正整数D,其中weights代表一系列货物，weights[i]的值代表第i件物品的重量，货物不可分割而且必须安装顺序运输，请你计算货船能够在D天内运完所有货物的最低运载能力
• 我们这道题和上道题一样，先来分析，运载重量至多是多少？至少是多少?

至少:max(weights),因为一旦小于这个值，根本不可能运完这个货

至多:sum(weights),这样的一天就可以运完

• 要求的是最小载重，所以可以用搜索左侧边界的二分搜索算法优化线性搜索

    public int shipWithinDays(int[] weights, int days) {
        int[] maxAndSum = getMaxAndSum(weights);
        int left = maxAndSum[0],right = maxAndSum[1]+1;
        //定义搜索区间[left,right),right不可达
        while (left<right){
            int mid = left + (right-left)/2;
            if(canFinish(weights,days,mid)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
    private int[] getMaxAndSum(int[] weights){
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int weight : weights) {
            max = Math.max(max,weight);
            sum += weight;
        }
        int[] ans = new int[2];ans[0] = max;ans[1]=sum;
        return ans;
    }
    //如果载重为cap,能否在D天内运完货物
    private boolean canFinish(int[] weights,int days,int cap){
        int i = 0;
        for(int day = 0 ;day<days;day++){
            //初始化载重
            int maxCap = cap;//表示这一天的运载量,然后开始装货
            while ((maxCap -= weights[i]) >= 0){//不断装货,一旦<了就是当天的运载量到极限了不能再装了
                i++;
                if(i == weights.length){
                    return true;
                }
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

5.4 如何高效解决接雨水问题

5.4.1 问题描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FoRI2ysT-1661782052076)(./image/jys.png)]

• 给你输入一个长度为n的nums数组代表二维平面内一排宽度为1的柱子，每个元素nums[i]都是非负帧数，代表第i个柱子的高度，现在请你计算，如果下雨了，这些柱子能够装下多少雨水?

5.4.2 核心思路

• 当发现这个问题对自己而言完全没有思路的时候，通常是因为我们站在了整体了角度来看问题了，导致问题的复杂度被放大，这时候我们不妨仅仅考虑局部，从局部入手，就像处理字符串一样，不要考虑如何处理整个字符串，而是应该考虑如何处理每一个字符
• 我们之前觉得难是因为我们看到了整个数组，那么现在我们从单个元素出发，我们以题图的i=4分析,当i=4的时候能装几个水?这时候很容易找到它能装两个水
• 这两个水是怎么得出来的呢?从i=4向左看，左边最高的柱子高度是2，向右看，右边最高的柱子高度是3，二者取小，以小的那个为限制，然后i=4的对应柱子高度为0，所以2-0，就是两个水

将上述过程用代码表示出来就是

water[i] = Math.min(
	//左边最高的柱子
    Math.max(height[0...i])
    //右边最高的柱子
    Math.max(height[i...n-1])
) - height[i]
1
2
3
4
5
6

• 暴力算法

    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        for(int i = 1;i<n-1;i++){
            int lMax = 0,rMax = 0;
            //找右边最高的柱子
            for(int j = i;j<n;j++){
                rMax = Math.max(rMax,height[j]);
            }
            //找左边最高的柱子
            for(int j = i;j>=0;j--){
                lMax = Math.max(lMax,height[j]);
            }
            //计算能够装的水
            ans += Math.min(lMax,rMax) - height[i];
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.4.3 备忘录优化

• 之前的解法中，每次都要计算height[0...i]之间的最大值，而且是通过循环遍历来求解的，但是细想一下，如果我们知道了height[0...i-1]，是不是再和height[i]比较一下，是不是就能够知道height[0....i]呢

• 思路:开两个数组rMax和lMax充当备忘录，其中定义:lMax[i]表示height[0...i]中最高柱子的高度，rMax[i]表示height[i...n-1]最高柱子的高度,注意base-case,lMax[0] = height[0],rMax[n-1] = height[n-1]

    public int trap(int[] height) {
        if(height.length == 0){
            return 0;
        }
        int n = height.length;
        int ans = 0;
        int[] lMax = new int[n];lMax[0] = height[0];
        int[] rMax = new int[n];rMax[n-1] = height[n-1];
        //从左向右计算lMax
        for(int i =1;i<n;i++){
            lMax[i] = Math.max(height[i],lMax[i-1]);
        }
        //从右向左计算rMax
        for(int j = n-2;j>=0;j--){
            rMax[j] = Math.max(height[j],rMax[j+1]);
        }
        //计算答案
        for(int i =1;i<n-1;i++){
            ans += Math.min(lMax[i],rMax[i])-height[i];
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5.4.4 双指针解法

• 这种解法的思路和前面的思路是完全一致的，但是在实现手法很巧妙，主要区别是备忘录提前计算预处理了，而双指针是边走边算，节省下空间复杂度

核心代码

    public int trap(int[] height) {
        if(height.length == 0){
            return 0;
        }
        int n = height.length;
        int ans = 0;
        int left = 0;
        int right =n-1;
        int lMax = height[0];//lMax是height[0...left]中最高柱子的高度
        int rMax=height[n-1];//rMax是height[right...n-1]的最高柱子的高度
        while (left<=right){
            lMax = Math.max(lMax,height[left]);
            rMax = Math.max(rMax,height[right]);
            //ans += Math.min(lMax,rMax)-height[i]
            if(lMax < rMax){
                ans += lMax- height[left];
                left++;
            }else{
                ans += rMax - height[right];
                right--;
            }
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 解法分析

回顾之前的备忘录解法,lMax[i]和rMax[i]代表的是height[0...i]和height[i...n-1]的最高柱子的高度

在此双指针解法中，lMax和rMax代表的是height[0...left]和height[right...n-1]的最高柱子的高度

此时lMax肯定是left指针坐标最高的柱子，但是rMax不一定是left指针右边的最高的柱子(根据定义)

我们只在乎min(lMax,rMax)，我们来思考一下，什么样的情况可以确保我们求出来的这格水一定是对的

我们知道对于left指针而言，其左侧的lMax肯定是height[left]左边的最高的柱子，如果我们想要确定这格水的存放，我们必须要知道右边所对应柱子的最高高度，这时候有两种情况

[1] 这时候遍历产生的右边所对应的柱子的最高高度比左边的最高高度要高，这时候可以确定，只能装lmax-height[left]了

高柱子的高度

此时lMax肯定是left指针坐标最高的柱子，但是rMax不一定是left指针右边的最高的柱子(根据定义)

我们只在乎min(lMax,rMax)，我们来思考一下，什么样的情况可以确保我们求出来的这格水一定是对的

我们知道对于left指针而言，其左侧的lMax肯定是height[left]左边的最高的柱子，如果我们想要确定这格水的存放，我们必须要知道右边所对应柱子的最高高度，这时候有两种情况

[1] 这时候遍历产生的右边所对应的柱子的最高高度比左边的最高高度要高，这时候可以确定，只能装lmax-height[left]了

[2] 这时候遍历产生的右边所对应的柱子的最高高度比左边的最高高度要矮，这时候可以确定，对于right指针而言，其装的水的主要制约因素是右边，因此这时候能确定height[right]