二分查找之「最大值极小化」例题选讲

2,232 阅读6分钟

写在前面的话:在 《二分查找之「最大值极小化」相关问题及解题步骤》 这个分享里,我们通过「力扣」第 410 题:「分割数组的最大值」详细讲解了这一类问题的思路分析、解题步骤、参考代码。并且给出了 55 道问题。

今天的分享就是这 55 道问题的思路分析和参考代码,供大家复习。

希望借着这篇推文能够帮助大家加深对这一类问题的敏感性,我们再为大家强调一下:

  • 搜索一个有范围的整数,可以用二分;
  • 分析题目中的单调性,通常这种单调性表现为两个变量此增彼减,即 负相关
  • 题目中 连续正整数 这两个前提缺一不可,非常非常重要,希望大家能够抓住题目中这两个关键信息,进而理解这种做法的有效性。

再次强调:写对二分查找不能靠模板,需要理解加练习。为了避免增加大家的阅读负担,并抓住重点,头两题我会把分析过程写得详细一点,后三题留给大家。


例 1:「力扣」第 875 题:爱吃香蕉的珂珂

分析题意:哪一堆香蕉先吃是无关紧要的,每一堆香蕉的根数是正数,符合「连续」、「正整数」条件。

一句话题解:如果目前尝试的速度恰好使得珂珂在规定的时间内吃完香蕉的时候,还应该去尝试更小的速度是不是还可以保证在规定的时间内吃完香蕉。

参考代码

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 - left) / 2;
            if (calculateSum(piles, mid) > H) {
                // 耗时太多,说明速度太慢了,下一轮搜索区间在 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索区间在 [left, mid]
                right = mid;
            }
        }
        return left;
    }

    /**
     * 如果返回的小时数严格大于 H,就不符合题意
     *
     * @param piles
     * @param speed
     * @return 需要的小时数
     */
    private int calculateSum(int[] piles, int speed) {
        int sum = 0;
        for (int pile : piles) {
            // 上取整可以这样写
            sum += (pile + speed - 1) / speed;
        }
        return sum;
    }

    public static void main(String[] args) {
//        int[] piles = {3, 6, 7, 11};
//        int H = 8;

//        int[] piles = {30, 11, 23, 4, 20};
//        int H = 5;

        int[] piles = {30, 11, 23, 4, 20};
        int H = 6;
        Solution2 solution = new Solution2();
        int res = solution.minEatingSpeed(piles, H);
        System.out.println(res);
    }
}

复杂度分析(后面的问题的复杂度分析一模一样,故全部略去):

  • 时间复杂度:O(Nlogmax(piles))O(N \log \max(piles)),这里 NN 表示数组 piles 的长度。我们在 [1,maxpiles][1, \max{piles}] 里使用二分查找定位最小速度,而每一次执行判别函数的时间复杂度是 O(N)O(N)
  • 空间复杂度:O(1)O(1),算法只使用了常数个临时变量。

例 2 :「力扣」第 1011 题:在 D 天内送达包裹的能力

分析题意:我们装载的重量不会超过船的最大运载重量(找一个有范围的整数),返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力(最大值最小化)。

题目中 按给出重量的顺序 这个条件非常重要,保证连续性。运输重量是正数。

  • 重点 1:货物必须按照给定的顺序装运;
  • 重点 2:最低运载能力:表示超过了就要另外起一艘航船。

运载能力最低是数组 weights 中的最大值,至少得拉走一个。最高是数组 weights 中的和。

一句话题解:单调性是:运载能力越低,需要的天数越多;运载能力越高,需要的天数越少。如果目前尝试的 最低运载能力 恰好使得传送带上的包裹在 D 天(注意:恰好是 D 天)从一个港口运送到另一个港口,还应该继续尝试减少 最低运载能力

参考代码

public class Solution {

    public int shipWithinDays(int[] weights, int D) {
        int maxVal = 0;
        int sum = 0;

        for (int weight : weights) {
            maxVal = Math.max(maxVal, weight);
            sum += weight;
        }

        int left = maxVal;
        int right = sum;
        while (left < right) {
            // 运载能力
            int mid = left + (right - left ) / 2;
            // 运载能力越大,天数越少
            // 运载能力越小,天数越多
            // 负相关
            if (calculateDays(weights, mid) > D) {
                // 太多,下一轮搜索区间 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索区间 [left, mid]
                right = mid;
            }
        }
        return left;
    }

    /**
     * 返回多少天
     *
     * @param weights
     * @param capacity
     * @return
     */
    private int calculateDays(int[] weights, int capacity) {
        int days = 1;
        int currentWeightSum = 0;
        for (int weight : weights) {
            if (currentWeightSum + weight > capacity) {
                currentWeightSum = 0;
                days++;
            }
            currentWeightSum += weight;
        }
        return days;
    }

    public static void main(String[] args) {
        int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int D = 5;

        Solution solution = new Solution();
        int res = solution.shipWithinDays(weights, D);
        System.out.println(res);
    }
}

例 3:「力扣」春季团体赛第 3 题:LCP 12. 小张刷题计划

题意分析:题目中强调了 必须按照顺序做完题目(连续),并且做题数量这件事情肯定是正数。

一句话题解:每天耗时最多的问题留给小杨去做。

参考代码

public class Solution {

    public int minTime(int[] time, int m) {
        int sum = 0;
        for (int num : time) {
            sum += num;
        }

        int left = 0;
        int right = sum;

        while (left < right) {
            int mid = (left + right) >>> 1;
            // mid 是 T 值的意思
            int splits = split(time, mid);
            if (splits > m) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int split(int[] nums, long maxSum) {
        int splits = 1;

        int len = nums.length;
        int curMax = nums[0];
        int tempSum = nums[0];

        for (int i = 1; i < len; i++) {
            curMax = Math.max(curMax, nums[i]);
            if (tempSum + nums[i] - curMax > maxSum) {
                tempSum = 0;
                curMax = nums[i];
                splits++;
            }
            tempSum += nums[i];
        }
        return splits;
    }
}

例 4:「力扣」第 1482 题:制作 m 束花所需的最少天数

题意分析:依然是题目用着重号强调了「需要使用花园中 相邻的 k 朵花」(连续),并且花朵数量这件事情肯定是正数。

分析单调性和左右逼近留给读者。

参考代码

public class Solution {

    public int minTime(int[] time, int m) {
        int sum = 0;
        for (int num : time) {
            sum += num;
        }

        int left = 0;
        int right = sum;

        while (left < right) {
            int mid = (left + right) >>> 1;
            // mid 是 T 值的意思
            int splits = split(time, mid);
            if (splits > m) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int split(int[] nums, long maxSum) {
        int splits = 1;

        int len = nums.length;
        int curMax = nums[0];
        int tempSum = nums[0];

        for (int i = 1; i < len; i++) {
            curMax = Math.max(curMax, nums[i]);
            if (tempSum + nums[i] - curMax > maxSum) {
                tempSum = 0;
                curMax = nums[i];
                splits++;
            }
            tempSum += nums[i];
        }
        return splits;
    }
}

例 5:「力扣」第 1552 题:1552. 两球之间的磁力

题意分析:距离这件事情天然具有连续性,并且距离肯定是正数。并且题目都告诉我们要我们求「最大化的最小磁力」,很显然往「最大值极小化」这一类问题上靠。

分析单调性和左右逼近留给读者。

参考代码

import java.util.Arrays;

public class Solution {

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int len = position.length;
        int left = 1;
        int right = position[len - 1] - position[0];

        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (countSplits(position, mid) >= m) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private int countSplits(int[] position, int distance) {
        int len = position.length;
        int pre = position[0];

        int M = 1;
        for (int i = 1; i < len; i++) {
            if (position[i] - pre >= distance) {
                M++;
                pre = position[i];
            }
        }
        return M;
    }
}