前言

在这篇文章中,我们将会一起学习二分算法,比上一章的滑动窗口要难上许多(对我来说)。

话不多说,我们直接开始。

1.二分算法的基本定义

一句话概括本质:通过判断左右边界所围成区域的中点的值和目标值的关系,来决定下一步要在该区域的哪半边继续进行同样的操作,直到触发循环的退出条件。

讲一讲流程就是(以左右闭区间为例):假设我们拿到一个升序的序列nums和要查找的目标值target,那么我们开局将左边界left和右边界right都设立在这个序列的两头(举个例子,0len(nums)-1),进入循环后先取它的中点mid,判断nums[mid]的值:

如果nums[mid]≥target,那就选择左半边进行下一步,使right=mid-1;反之,选择右半边进行下一步,使left=mid+1

周而复始,直到触发循环的退出条件(此处是left>right退出)。

2.如何进一步理解二分算法-红蓝染色法

可以先去看这个视频:【算法入门】用红蓝染色法学爆二分查找

在红蓝染色法中,我们将一个升序数组分成蓝区(<目标值的区域),空白区和红区(>=目标值的区域)。我们二分就是把对应的元素染色到对应的区域。

在这个视频中,博主介绍了三种二分类型,分别是左右开区间、左右闭区间以及左闭右开区间。为了方便,本文章统一使用左右闭区间,即[l,r]。

在这个视频中,左右闭区间类型的二分算法在循环结束后,有一件事情是永远不变的,无论红蓝区的标准如何调整:l在红区的最左边,r在蓝区的最右边。如下图所示:

l,r在结束循环后的位置关系

并且,按照我上面的分区设定,l会正好指在target上面(如果有),如果没有target,会指在大于它的第一个数上面。所以如果你要找target或者大于它的第一个数,直接输出nums[l]就行了。

那么遇到其他类型又怎么办呢?假设题目就是想让我找>target的第一个数,并且nums中有可能本身就有target,如果还是按照上面的标准划定红蓝区,那么就有可能直接输出target了,这咋整呢?

先记住上面永远不变的事情,然后我们再去调整蓝区和红区的标准,就能做到这件事:把红区调整成>target的数全都在这里面,把蓝区调整成≤target的数全都在这里面。再看看上面永远不变的事情,是不是l自然而然就指到了比target大的第一个数上,并且即使有target,也不会指到target上。

那么反映到代码上,又会变成咋样呢?

先看看最上面情况的代码(蓝区是<目标值的区域,红区是>=目标值的区域):

    int lower_bound(vector<int>& nums,int target){
        int l=0,r=nums.size()-1;
        while (l<=r){
            int mid=(l+r)/2;
            //下面这一行代码是最关键的,是决定红蓝区域性质的核心代码
            if (nums[mid]<target){ //由于l左边(不包含它自己)是蓝区,如果nums[mid]<target,
                l=mid+1; //那么将其收入蓝区;
            }else{ //如果nums[mid]≥target,
                r=mid-1; //将其收入红区
            }
        }
        return l;//输出红区的最左边的元素
    }

结合注释看,你现在一定有所体会了吧?所以,如果我们要求大于target的第一个数,那就按照上面的标准来更改红蓝区:把红区调整成>target的数全都在这里面,把蓝区调整成≤target的数全都在这里面。

    int lower_bound(vector<int>& nums,int target){
        int l=0,r=nums.size()-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (nums[mid]<=target){ //由于l左边(不包含它自己)是蓝区,如果nums[mid]<=target,
                l=mid+1; //那么将其收入蓝区;
            }else{ //如果nums[mid]>target,
                r=mid-1; //将其收入红区
            }
        }
        return l;//输出红区的最左边的元素
    }

这样一讲,是不是小于target的第一个数等等情况,你也能解决了?

如果要找小于target的第一个数,就直接将蓝区改成<target,红区改成≥target,最后l-1就是答案的位置(如果算出来是-1,说明不存在,target就是最小的数)。

其他情况就不讲了,举一反三即可。

3.题目实战——二分查找型 0809更新

做了4天的题目(当然也只限于白天的时间做,晚上或者接近晚上时我要三角洲启动),属于是要给我燃尽了。这个难度真的比滑动窗口难多了。滑动窗口是这样的:简单题直接秒,中等题有的能秒有的得稍微想想,hard题目有点难度,有的能想出来,没想出来的看题解后也能豁然开朗;二分呢?简单题我得想想到底哪里能用到二分,中等题我绞尽脑汁,hard题连题解也看不懂。

二分做题情况

别问我为啥中间空着一些题目没做,大部分的题目都是涉及到类(class)等等的概念(除了3488和两道会员题之外其他都是),我连题意都难以理解,更别说做出来了。等其他正常的算法题做完之后,我再回过头来学习学习类的概念,在其他类型题目的章节中挑几题讲讲。

在做出来的题目之中,以下题目是我没使用二分算法做出来的,因为我没想到哪里能用到二分,所以也排除在此次讲解名单之外:

  1. 1385. 两个数组间的距离值
  2. 2389. 和有限的最长子序列
  3. 658. 找到 K 个最接近的元素

感兴趣的同学可以自己去做做看。排除掉上面这些题目,剩下的题目,我来挑一些讲解。除了简单题,中等及以上的都有一个共同特质:都是10^5的数据规模,必须要利用二分去卡nlogn的时间复杂度,否则就超时。

那我们先从简单题开始吧。

3.1 简单题:利用红蓝染色法掌控left指针最终落点

由于在第二个章节中,我已经将红蓝染色法讲的比较细致了,所以我在这里题目的讲解中会一笔带过。

先看第一题:34. 在排序数组中查找元素的第一个和最后一个位置

这道题要求我们找到升序数组中重复元素所在的区间。换句话说,我们只需要二分两次,第一次确定该元素最开始的点位,第二次确定比该元素大1的元素的位置。是时候请出红蓝染色法了!

设定红蓝规则如下:蓝区包含<target的数,红区包含>=target的数,由于left指针一定会落在红区的最左边第一位,所以left指向的要么是target,要么是比target大的第一个数。

所以在我们的第一次二分中,直接取left就是该元素的左区间。再加个判断:如果nums[left]≠target或者left超出了数组右边界1格,说明不存在该元素,我们直接返回[-1,-1],都不需要做第二次二分了。

如果第一次二分找到了,没退出,那就继续第二次二分。我们需要找到该元素的右边界。继续沿用上面的红蓝规则,我们直接代入target+1,这样最后left一定会停在target+1这个数或者比target+1大的第一个数上,那此时的left-1就一定是target。这时候就不需要判断了,left最多超出数组右边界1格,left-1是一定在界内的(建立在第一次二分合法的前提下)。

看代码:

class Solution {
public:
    int lower_bound(vector<int>& nums, int target){
        int l=0,r=nums.size()-1;
        while (l<=r){
            int mid = (l+r)/2;
            if (nums[mid]<target){ //因为left左边是蓝区
                l = mid+1; //所以按照职责的划分,小于target的数会被l扫过去,进入蓝区,包括nums[mid]本身
            }else{ //二分代码的核心就在这几行,别的没啥好讲解的
                r = mid-1;
            }
        }
        return l;
    }
    vector<int> searchRange(vector<int>& nums, int target) { //解题主程序
        int start = lower_bound(nums,target); //查找该元素左边界
        if (start==nums.size() || nums[start]!=target){ //按照上面所说的,进行合法性判定
            return vector<int>{-1,-1}; //若非法,说明没找到
        }
        int end = lower_bound(nums,target+1)-1; //按照上面所说的,找右边界
        return vector<int>{start,end};
    }
};

剩下的基础题目中,下列题目都是和本题一样的红蓝规则,我就不重复讲解了:

  1. 35. 搜索插入位置
  2. 2529. 正整数和负整数的最大计数

但是有一道题是例外,它的红蓝规则和本题一样,但是我用到了一个新东西——保存答案并提前退出

请看第二题704. 二分查找

其实呢,这道题不用这个新东西也是能做的,就是稍微麻烦一点:在循环退出后,判断left指针是否越界、指向的是不是target,如果是就说明找到了,否则就是没找到。

但是,用了这个方法后,我们只需要起一个ans变量,令它初始等于找不到就要返回的值(本题是-1),并且在二分的判断中插入一条对nums[mid]是否等于target的判断语句,如果是,就将mid存入ans,然后直接break。事后不需要任何判断,直接就能返回ans。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1,ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (nums[mid]<target){ //一样的红蓝规则
                l=mid+1;
            }else if (nums[mid]==target){ //中途插入是否相等的判断
                ans=mid;
                break;
            }else{
                r=mid-1;
            }
        }
        return ans;
    }
};

接着我们来讲第三题744. 寻找比目标字母大的最小字母。这题的红蓝规则和前面两题不一样,让我们一步步来寻找新的规则。

它要找比目标字母大的第一个字母,也就是我就算找到了目标字母,也不行,得去找比它大的第一个字母。

这种情况下,我们直接令红蓝规则如下:蓝区包含<=target的字母,红区包含>target的字母。

由于left一定会落在红区最左边第一个,所以自然而然就落在了比目标字母大的第一个字母上。是不是非常巧?

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int l=0,r=letters.size()-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (letters[mid]<=target){ //蓝区包含<=target的字母
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        if (l==letters.size()){ //如果left超出了数组右边界,说明没找到
            return letters[0]; //按照题目要求返回第一个字母
        }
        return letters[l];
    }
};

至此,二分查找的基础题目已经过了一遍。如果上面3题全都掌握,那么你已经基本上掌握了红蓝染色法的精髓。

3.2 中等题以及hard题:nlogn是我的底线

这一部分的题目,我很难去归纳出几种类型。因为这和上一个滑动窗口的难题一样,重点不在二分查找本身,而是你不知道你该拿二分查找去干啥,在动用二分查找之前该如何转换题目的条件。

所以,如果强行归纳,那么这些题目有一个共同点:拿一连串的询问去一串数组里面二分查询啥东西,并且还把排序这个数组的工作交到了你手上,时间复杂度nlogn,别的没了。

所以,学会使用各个主流竞赛语言的内建排序方法还是非常重要的,下面来盘点一下。

3.2.1 各个主流竞赛语言的内建排序方法

1.c++的内建排序方法

int main(){
    vector<int> nums = {1,1,4,5,1,4}; //初始化数组
    sort(nums.begin(),nums.end());//升序排序
    sort(nums.begin(),nums.end(),[](auto& a,auto& b){ //降序排序
        return a>b; //此处使用lambda规则,其中a和b代指前一个元素和后一个元素,a>b即为我希望前一个比后一个大,实现降序排序
    });
}

2.c++使用lambda对二维数组进行自定义排序

当然这里可以灵活应变,换成pair也是可以的。cpp的lambda还是比较好理解的,我是直接死记硬背的,反正目前就这个场景会用到。

int main(){
    vector<vector<int>> matrix = {{1,2,3},{5,4,6},{8,9,7}};
    sort(nums.begin(),nums.end(),[](auto& a,auto& b){ //这里的a和b代指拨开matrix的第一层元素,即{1,2,3}这样的
        return a[0]<b[0]; //这里的意思是取第一位进行比较,即按照第一位的大小进行降序排序
    })
}

3.python的内建排序方法(包含lambda自定义排序语句,若有不懂,请先去学习python的lambda语句)

nums = [1,1,4,5,1,4]
nums.sort() #升序排序,直接改变nums本身
nums.sort(reverse=True) #降序排序
sortedNums = sorted(nums) #升序排序,不直接改变nums本身,需要自己拷贝
sortedNums = sorted(nums,reverse=True) #降序排序,不直接改变nums本身,需要自己拷贝
matrix = [[1,2,3],[4,5,6],[7,8,9]]
matrix.sort(key=lambda x:x[0]) #此处是按照子列表的第一个数的大小进行升序排序
matrix.sort(key=lambda x:x[0],reverse=True) #此处是按照子列表的第一个数的大小进行降序排序

4.Go的内建排序方法

不讲它的自定义排序了,纯纯路边,竞赛用这个纯属浪费时间。想学的去滑动窗口的文章里面找,那里面有。

  • sort.Ints([]int)
    升序排序 int 切片。
  • sort.Float64s([]float64)
    升序排序 float64 切片。
  • sort.Strings([]string)
    升序排序 string 切片。

不多说。

3.2.2 正式开始题目实战

首先看第一题1170. 比较字符串最小字母出现频次

我们需要分成两步来解决这个题目。首先解决这个f(s)函数,再利用这个函数去解决题目的问题。

如何写这个f(s)函数呢?在这道题目,由于用例比较水,所以你直接遍历数次数也是可以的。但是我们这次学的是二分算法,所以我们可以先排序,后二分:将字符串按照字母序升序排序后,利用二分找重复字母的左边界和右边界,然后减一减就是出现次数(和上面34. 在排序数组中查找元素的第一个和最后一个位置是一样的)。

int f(string s){
    //1.给字符串排序 aaazz
    sort(s.begin(),s.end());
    //2.找最小字母
    char target = s[0];
    //3.二分找边界
    int l = 0,r = s.size()-1;
    while (l<=r){
        int mid = (l+r)/2;
        if (s[mid]<=target){ //<=的放蓝区
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    return l; //左边界最终落点即为出现次数
}

接下来开始解决题目要求的问题。我们可以看到,题目中的比较都是f(s)求值后的数字之间的比较,所以我们需要先遍历querieswords,一个个调用f(s)将其转换成频率的数值并存入数组。接下来我们只需要对着两个数组处理问题即可。

接下来,我们需要获取需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目,并且W 表示词汇表 words 中的每个词。这说明我们可以继续使用二分——一个个取出queries[i],事先将words数组排序好,然后用二分去找queries[i],设定蓝区为<=,红区为>,这样最后left一定指向大于 f(queries[i]) 的第一个数。最后再用数组长度-left,直接得出答案。

class Solution {
public:
    int f(string s){}//此处省略,同上
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        //1.把queries和words全部转换成数组
        vector <int> qs,ws,ans;
        for (int i=0;i<queries.size();i++){
            qs.emplace_back(f(queries[i]));
        }
        for (int i=0;i<words.size();i++){
            ws.emplace_back(f(words[i]));
        }
        //2.给ws排序
        sort(ws.begin(),ws.end());
        //3.单独拎出qs,一个个和ws对比
        for (int i=0;i<qs.size();i++){
            int k = qs[i],l = 0,r = ws.size()-1;
            while (l<=r){
                int mid = (l+r)/2;
                if (ws[mid]<=k){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }
            ans.emplace_back(ws.size()-l);
        }
        return ans;
    }
};

接下来来到难度上升的第二题2563. 统计公平数对的数目

这道题,我们需要解决如何计算符合条件的对数。仔细看看题目条件:lower <= nums[i] + nums[j] <= upper,且0 <= i < j < n——按照以往的做题经验,我们只需要揪住其中一个不放,让另一个动起来就行了。否则两个都在动,我们不好处理。那么具体怎么操作呢?

看看数据规模,依旧是我们熟悉的10^5,这注定我们的时间复杂度不能超过nlogn,自然而然想到了第一层枚举+第二层二分。我们将nums[i]移项到两边,这样我们的不等式就变成了lower-nums[i] <= nums[j] <= upper-nums[i],这样我们不是只需要找到符合条件的nums[j]就行了?这样我们就形成了一个基本框架:将数组提前排序好,一层循环遍历找nums[i],二层二分找符合条件的nums[j]的左边界和右边界,这样我们就能在规定的时间复杂度内完成这道题目。

接下来来解决第二个问题:我们该设定咋样的红蓝规则来找到左右边界呢?为了方便,我们规定我们所寻找的是闭区间(像[1,3]这样的),在本题中,就是[lower-nums[i],upper-nums[i]]这样的区间。先找左边界的位置,我们令蓝区为<,红区为>=,这样left天然就会落在左边界上;再找右边界,我们令蓝区为<=,红区为>,这样left-1就一定会落在右边界的位置。由于上面对红蓝染色法铺垫了太多,此处我讲的十分简略。如果这里你看不懂,退回去从头开始看就行了(那个视频也要看)。

这样,我们就知道该如何寻找符合条件的数的左右边界了。接下来还有最后一个问题——计算组数,这也是个难点。由于组数和两个数字的顺序无关,所以为了防止重复,我们只关注第一层枚举出来的数的后面的数,这个数后面有几个符合条件的数,我们就将其与这个数连线,就构成了几个数对。由于我们二分查找的范围是整个数组,有时候left边界甚至left、right两个边界会一起跑到我们枚举的i的左边去,这时候就需要我们加以判断并做出处理,这是决定这道题目能不能做对的关键。

首先,如果left超出数组的边界咋整?这说明这个数组里面的数都太小了,没一个数是能符合lower-nums[i]的标准的,这种情况直接跳过,没一个能累加的。其次,如果right<=i呢?按照我们上面不重复的原则,这样也是不能累加的。那么,如果i被夹在left和right中间呢?此时,只需要取max(left,i+1)作为左边界就行了,我们需要主动舍弃<i+1的部分,因为这样会重复。

至此,本题思路讲述完毕,比上一题多了一些巧思,尤其在边界处理上还是有些难度,上代码:

class Solution {
public:
    long long upper_bound(vector<int>& nums, int upper){ //找右边界
        int l=0,r=nums.size()-1;
        while (l<=r){
            int mid = l+(r-l)/2;
            if (nums[mid]<=upper){
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return l-1;
    }
    long long lower_bound(vector<int>& nums, int lower){ //找左边界
        int l=0,r=nums.size()-1;
        while (l<=r){
            int mid = l+(r-l)/2;
            if (nums[mid]<lower){
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return l;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        //1.给nums排序
        sort(nums.begin(),nums.end());
        //2.开始二分找合格的数字的范围并累加
        long long sum = 0;
        for (int i=0;i<nums.size()-1;i++){
            int k = nums[i],low = lower-k,up = upper-k; //这里是对原不等式的移项操作
            int left = lower_bound(nums,low);
            int right = upper_bound(nums,up);
            if (left>=nums.size() || right<=i){ //很重要的判断
                continue;
            }
            sum+=right-max(left,i+1)+1; //处理i夹在l和r中间的情况
        }
        return sum;
    }
};

接下来来到第三题LCP 08. 剧情触发时间

这道题比第二题略微简单一些,和第一题难度差不多,这是我主观上的感受,因为我想了一会也算是想出来了。

主要思路就是这样:把每日的递增量累加起来,自然而然就形成了一个每个值都上升的二维数组;然后单独拎出每个剧情触发的要求requirements[i],里面有三个数,我们再单独拎出其中的每个数requirements[i][j],使用二分找到它开始达标的第一天的位置(红蓝规则如下:蓝区<,红区>=,这样left的落点就是刚刚开始达标的第一天的位置),把三个数的位置都找出来并记录,最后选出最大(最靠右)的那个位置,就是3个全都达标的天数。这利用了每个值都上升的特性,只要前面达标了,不管多后面它都会达标。

这题是真正的巧思,如果没想到这一点,用其他方法我也不知道怎么做。上代码:

class Solution {
public:
    int betterMax(vector<int> nums){ //用来求数组最大值的函数
        int maxNum=nums[0]; //所以cpp和go能不能学一下python的max()?尤其是go
        for (auto x:nums){
            maxNum=max(maxNum,x);
        }
        return maxNum;
    }
    vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
        //1.写出自动升序的实时属性数量
        vector<vector<int>> curNum(increase.size()+1,vector<int>(3,0));
        for (int i=1;i<=increase.size();i++){
            for (int j=0;j<3;j++){
                curNum[i][j]=increase[i-1][j]+curNum[i-1][j]; //累加增量,此事在前缀和中亦有记载
            }
        }
        //2.遍历reqs
        vector<int> ans(requirements.size(),-1);
        for (int i=0;i<requirements.size();i++){
            vector<int> tempAns(3,0);
            bool flag = true; //触发器,如果其中有一个属性无法在规定天数内达到要求,就直接退出,没必要再算后面的属性了
            for (int j=0;j<3;j++){
                int req = requirements[i][j],l=0,r=curNum.size()-1;
                while (l<=r){ //二分找开始的天数
                    int mid = l+(r-l)/2;
                    if (curNum[mid][j]<req){
                        l = mid+1;
                    }else{
                        r = mid-1;
                    }
                }
                if (l>curNum.size()-1){ //如果left落在了最后一位,说明
                    flag=false;
                    break;
                }
                tempAns[j]=l;
            }
            if (!flag){
                continue;
            }
            ans[i]=betterMax(tempAns);
        }
        return ans;
    }
};

接下来来到第四题:2070. 每一个查询的最大美丽值,从这道题开始,还有下面的第五题,我都没想出来,看题解做出来的,好在题解也是看懂了。

看完题目了?那就先看题解吧:灵神的题解,看里面的方法二,方法一我没看懂。

方法二的精髓是这个《左侧最大值》的算法,这使得我们可以直接对着处理好的数组二分查找,十分方便。

看看我的代码:

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        //1.按照价格大小排序
        sort(items.begin(),items.end(),[](auto& a,auto& b){
            return a[0]<b[0];
        });
        //2.原地构建左边的最大美丽值
        for (int i=1;i<items.size();i++){
            items[i][1]=max(items[i-1][1],items[i][1]);
        }
        //3.二分查找价格的正确位置
        vector<int> ans(queries.size(),0);
        for (int i=0;i<queries.size();i++){
            int l=0,r=items.size()-1,k = queries[i];
            while (l<=r){
                int mid = l+(r-l)/2;
                if (items[mid][0]<=k){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }
            if (l-1>=0){ //这里依旧需要留心处理边界
                ans[i]=items[l-1][1];
            }
        }
        return ans;
    }
};

接下来来到本次讲解的最后一题,第五题1818. 绝对差值和

这题我依旧是没想出来,看了题解做出来的,请先阅读该题解

看完题解后,我豁然开朗,但是仍然有一点搞不明白:它为何不处理重复取元素的情况?毕竟nums1和nums12,后者排序了,去后者二分查找是极有可能找到一个和前者nums1[i]相等的元素的。

后面明白了:即使重复了又如何?重复找到了最小的元素,不就说明我不需要用别的元素替换自己吗。毕竟题目也没强制要求必须替换。

贴上我的代码:

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        //1.拷贝一份nums1,然后排序
        vector<int> nums12=nums1;
        sort(nums12.begin(),nums12.end());
        //2.对于nums1中的每一个元素,二分找和nums2[i]最接近的元素,并一直累加
        long long sum=0,mod=1000000007,maxDiff=-1;
        for (int i=0;i<nums1.size();i++){
            long long tempAns = abs(nums1[i]-nums2[i]),newAns=0;
            sum+=tempAns;
            int l=0,r=nums12.size()-1;
            while (l<=r){
                int mid = l+(r-l)/2;
                if (nums12[mid]<nums2[i]){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }
            if (l-1<0){ //
                newAns = abs(nums12[l]-nums2[i]);
            }else if (l>nums12.size()-1){
                newAns = abs(nums12[l-1]-nums2[i]);
            }else{
                newAns = min(abs(nums12[l]-nums2[i]),abs(nums12[l-1]-nums2[i]));
            }
            if (abs(tempAns-newAns)>maxDiff){
                maxDiff=abs(tempAns-newAns);
            }
        }
        //3.直接sum-最大值就是答案
        return (sum-maxDiff)%mod;
    }
};

至此,这一章节已经全部更新完毕。

4.题目实战——二分答案型

4.1 求最小 0814更新

4.1.1 简介

这一部分的题目,一句话概括:用二分算法去猜答案,然后再通过时间复杂度O(n)及以内的算法来判断我猜出来的答案对不对,再通过算法的计算结果来判断答案是大了还是小了,直到退出二分,即获得答案。

下面放一个偷来的代码模板,能很完美的概括这一系列的题目:

class Solution:
    # 计算满足 check(x) == True 的最小整数 x
    def binarySearchMin(self, nums: List[int]) -> int:
        # 二分猜答案:判断 mid 是否满足题目要求
        def check(mid: int) -> bool:
            # TODO

        left =   # 循环不变量:check(left) 恒为 False
        right =   # 循环不变量:check(right) 恒为 True
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            if check(mid):  # 说明 check(>= mid 的数) 均为 True
                right = mid  # 接下来在 (left, mid) 中二分答案
            else:  # 说明 check(<= mid 的数) 均为 False
                left = mid  # 接下来在 (mid, right) 中二分答案
        # 循环结束后 left+1 = right
        # 此时 check(left) == False 而 check(left+1) == check(right) == True
        # 所以 right 就是最小的满足 check 的值
        return right

二分答案做题情况

这次的题目在前面也是偏简单的,主要是后面的一些题目真的挺难的。尤其是最后一题,我看题解也理解了半天。

其实二分算法本身是一样的,这种类型的题目,主要就两个难点:第一个,也是最主要的,就是判断答案是否正确的算法,这是区分各个题目的一个东西;第二个,就是对二分算法上下界的判断,也基本得预先处理题目中的数组才能给出明确的上下界。

我将上面的题目分为以下几类(是我自己做题的主观感受,如果想要客观评价,上方图片的顺序就是由简单到难)

1.基础题(我能较快做出来)

1283. 使结果不超过阈值的最小除数

2187. 完成旅途的最少时间

1011. 在 D 天内送达包裹的能力

875. 爱吃香蕉的珂珂

2.进阶题(我需要思考一下才能做出来)

3639. 变为活跃状态的最小时间 和 滑动窗口->不定长滑窗->求子数组个数->越长越合法 知识点梦幻联动(至少我的做法是这样) 讲解

1482. 制作 m 束花所需的最少天数 这应该是没有固定模板,手搓的检查算法

2594. 修车的最少时间 这题我也是受下面3296的启发才做出来的,如果没受启发,难度应该介于进阶和困难之间,比3296略简单

3.困难题(我想不出来,看了题解才能做出来)

3296. 移山所需的最少秒数 彻底干碎算法题目做太多的思维定式 讲解

475. 供暖器 又是一个新思路 讲解

4.地狱题(我看了题解还得理解很久,才能彻底弄懂)

3048. 标记所有下标的最早秒数 I 讲解

其中会讲解的题目也已经在上面标记了出来。

4.1.2 部分题目的讲解

先讲解第一题3639. 变为活跃状态的最小时间,先看题。

关键部分:

如果 子字符串 包含 至少 一个 '*' ,则认为该子字符串有效。

如果字符串中 有效子字符串 的总数大于或等于 k,则称该字符串为 活跃 字符串。

看到这两句,你是不是想起了什么?没想起来的自己去https://blog.lecspace.com/index.php/archives/76/复习一下。

不卖关子了,这就是 滑动窗口->不定长滑窗->求子数组个数->越长越合法 这一部分的知识点。我们可以在第一层使用二分猜答案,再在第二层使用越小越合法的老知识点,对*进行计数,并数出满足上述条件的子数组个数,再把它和k比较,就完事。

看我的代码,有详细注释:

class Solution {
public:
    int minTime(string s, vector<int>& order, int k) { //解题主程序
        //1.找二分的上下界并初始化
        long long l = 0,r = order.size()-1,ans=-1;
        //2.开始二分
        while (l<=r){
            long long mid = l+(r-l)/2;
            string newS = s; //复制一份字符串便于我们处理
            for (int idx=0;idx<=mid;idx++){
                newS[order[idx]]='*'; //按照题目要求替换字符串
            }
            //滑窗数符合要求的子字符串数量
            long long left=0,cnt=0,count=0; //cnt是数*个数的,count是数符合条件的子数组个数的
            for (long long right=0;right<newS.size();right++){
                if (newS[right]=='*'){
                    cnt++;
                }
                while (cnt>=1){ //一直推到不符合条件为止
                    if (newS[left]=='*'){
                        cnt--;
                    }
                    left++;
                }
                count+=left;
            }
            //下面开始比较
            if (count>=k){ //字符串中有效子字符串的总数大于或等于k
                ans = mid; //事先记录下答案
                r = mid-1; //去尝试更小的
            }else{
                l = mid+1;
            }
        }
        return ans;
    }
};

接着来讲第二题3296. 移山所需的最少秒数,先看题。

看完题目了,先看一下我当时看的题解

这题属于是给我震惊到了。当时我看到题目的这个式子: workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x ,我第一时间想到的是去做一个前缀和,来处理1+2+3+...+x这个式子,然后后面就不知道该如何处理了。

首先,这个式子是一个很经典的等差数列,根本用不着前缀和,只需要用最经典的x(1+x)/2的等差数列求和公式就行了。

并且,我们二分的是答案——秒数。这个式子是算秒数的,如果你用前缀和,意味着你永远无法拆开这个式子,没法进行如题解一样的左右移项的操作,最终来达到化秒数这个结果成为能代入计算是否符合的变量

知道要拆开式子后,这道题目最后的难点就是处理上下限了。题解讲的很清楚了,此处不再赘述。

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        //1.先找上下界
        long long maxTime=workerTimes[0];
        for (auto x:workerTimes){ //这里枚举workerTimes是为了找到最大的时间,用于计算上界
            if (x>maxTime){
                maxTime=x;
            }
        }
        //2.开始二分答案
        long long l=1,r=maxTime*mountainHeight*(mountainHeight+1)/2,minTime=r; //此处的r就是和题解一样计算上界
        while (l<=r){
            long long mid = l+(r-l)/2,total=0;
            for (auto x:workerTimes){
                long long k=mid/x,sqr = floor(sqrt(8*k+1)); //按照题解的思路进行开方计算
                sqr = (long long)floor(sqrt(8.0L*k + 1.0L)); //此处要注意上下取整的处理
                total += (sqr - 1) / 2; //由于结果越大越好,为了确保合法性,我们选择下取整
                if (total >= mountainHeight) break; // 剪枝
            }
            if (total>=mountainHeight){ //经典的二分判断+结果记录
                minTime=min(minTime,mid);
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return minTime;
    }
};

看来做算法题,有时候也不能局限于算法技巧,数学上的一些知识也是可以运用的。

然后,来看看第三题475. 供暖器,先看题。

看完题目来看题解

这道题的题意还是比较好理解的,二分的目的性也很强,最主要的难点就是想出一个时间复杂度在O(n)之类的算法来验证我此次二分出来的半径是否合法。但是我怎么就是想不出来。

题解的思路也是非常新奇:直接摆脱传统二分模板,外层遍历每一个屋子,然后使用二分找离每个屋子最近的供暖器,然后每个屋子都遍历过去,维护一个距离的最大值,就是我们所求的最小半径。

看代码:

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        //1.升序排heaters
        sort(heaters.begin(),heaters.end());
        //2.遍历房屋,二分找离每个屋子最近的供暖器
        int maxRange=0;
        for (int i=0;i<houses.size();i++){
            int target = houses[i],l=0,r=heaters.size()-1;
            while (l<=r){ //二分找的是供暖器,不是答案
                int mid = l+(r-l)/2;
                if (heaters[mid]<target){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }
            if (l==0){ //这里处理left停在数组第一个位置的情况
                maxRange = max(maxRange,abs(heaters[l]-houses[i]));
            }else if (r==heaters.size()-1){//这里处理right停在数组最后一个位置的情况
                maxRange = max(maxRange,abs(heaters[r]-houses[i]));
            }else{ //如果l和r都合法,那就取其中最小值,代表离的最近的取暖器,然后全局再维护一个最大值
                maxRange = max(maxRange,min(abs(heaters[l]-houses[i]),abs(heaters[r]-houses[i])));
            }
        }
        return maxRange;
    }
};

最后,我们来看第四题3048. 标记所有下标的最早秒数 I,先看题。

看完题目了吗?是不是感觉题意很晦涩难懂?那么先不急着看题解,看看我偷来的别人对题目很形象的改写:

你有 n 门课程需要考试,第 i 门课程需要用 nums[i] 天复习。同一天只能复习一门课程。

在第 i 天,你可以选择参加第 changeIndices[i] 门课程的考试。考试这一天不能复习。

搞定所有课程的复习+考试,至少要多少天?

带着这个改写,再去想想。如果还是想不出来,那就看看题解吧。

这道题,虽说从框架上来看是经典的二分答案,但是判断这个天数够不够的过程还是非常反常规和难的。我对着这个题解写我自己的代码都费了好大一阵功夫。

class Solution {
public:
    bool check(vector<int>& nums, vector<int>& changeIndices,int maxDay){
        //找出每个下标的最后位置
        vector<int> last(nums.size(),0);
        for (int i=0;i<maxDay;i++){
            last[changeIndices[i]-1]=max(last[changeIndices[i]-1],i+1);
        }
        //找出最靠后的下标位置,用于初步判断天数合法性
        int maxPos=last[0];
        for (auto x:last){
            maxPos=max(maxPos,x);
            if (x==0){
                return false;
            }
        }
        if (maxDay<maxPos) return false; //初步判断题目所给数组合法性
        int cnt=0;
        for (int t=1;t<=maxDay;t++){
            if (last[changeIndices[t-1]-1]!=t){ //如果不是考试日
                cnt++;
            }else{ //如果是考试日
                if (cnt<nums[changeIndices[t-1]-1]){
                    return false;
                }
                cnt-=nums[changeIndices[t-1]-1];
            }
        }
        return true;
    }
    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
        if (nums.size()>changeIndices.size()) return -1;
        //1.确定上下界
        int l=1,r=changeIndices.size();
        //2.开始二分
        int ans=-1;
        while (l<=r){
            int mid = l+(r-l)/2;
            if (check(nums,changeIndices,mid)){
                ans = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return ans;
    }
};

4.2 求最大 0828更新

4.2.1 简介

好久不见。也是14天没更新了,因为最近事情比较多,类似于同学聚餐,亲戚拜访之类的,并且人也不在状态上,加上这一批的题目比上批难了不知道多少,于是做题速度就极其慢。经过14天的磕磕绊绊,我也总算是把我目前知识能解决的题目给做出来了,下面给这些题目分分类。求最大的二分框架,我就不另外介绍了,套路基本一致,不清楚的直接去看上面的4.1.1,把ans=mid下面这行的r=mid-1换成l=mid+1,下面else分支的也相应换过来就行了。

做题情况

我将上面的题目分为以下几类(是我自己做题的主观感受,如果想要客观评价,上方图片的顺序就是由简单到难)

1.基础题(我能较快做出来)

2226. 每个小孩最多能分到多少糖果 二分猜答案去直接遍历就行了,比较容易想到

2.进阶题(我需要思考一下才能做出来)

2576. 求出最多标记下标 这题我其实看提示了 需要想到匹配k个最小的数和k个最大的数之间的对应位置 不然做不出 此题会讲解

2982. 找出出现至少三次的最长特殊子字符串 II 联动滑动窗口知识

1898. 可移除字符的最大数目 需要手写一个逻辑去一个个匹配字母 以判断是不是子序列

1802. 有界数组中指定下标处的最大值 此题卡O(logn),强制你用等差数列求和公式去求和,找公式里面的首项、末项、项数三个参数非常麻烦,本来如果允许O(nlogn),直接使用循环求值,边界会比较好找

1642. 可以到达的最远建筑 基本逻辑不难:梯子留给最高的落差用,其他落差用砖块堆。但是要注意分类讨论细节

3.困难题(我想不出来,看了题解才能做出来)

275. H 指数 II 这题属于是看了题解能秒懂的类型:顺着题目的逻辑从小到大列举一下,就知道如何二分了 此题会讲解

2861. 最大合金数 当时做的时候定式思维了,没反应过来二分是需要顺着题目的思路去验证是否正确,而是一边二分一边在那里尝试直接求出数量。如果脑子转过来了这题其实属于进阶题里面最难的一题 此题会讲解

2071. 你可以安排的最多任务数目 这题是典型的贪心:用最强的k个工人去做最简单的k个任务,最好不嗑药就能做掉最简单的任务,实在不行要嗑药就做嗑药后能做的最难任务。贪心逻辑好理解,代码实际的实现略有难度 此题会讲解

4.地狱题(我看了题解还得理解很久,才能彻底弄懂)

2141. 同时运行 N 台电脑的最长时间 主要是得理解题解里面把电池电量当成连续的来用的思想 此题会讲解

5.78题(题解里面需要用到我目前没掌握的,且难以快速掌握的知识解决题目,所以看了题解也无法做出)

3007. 价值和小于等于 K 的最大数字 需要用到数位DP 后面学到了再来补

2258. 逃离火灾 需要用到双数组 并且我bfs只是初学 并不是很熟练 陆陆续续尝试了三四个小时没做出来

4.2.2 部分题目的讲解

第一题:2576. 求出最多标记下标,先看题。

先看是否符合二分要求:看到2 * nums[i] <= nums[j]这个式子,我们肯定想让左边的数字尽量小,右边的数字尽量大。这样配对后,剩下的数字会自然而然的越来越接近,也就是更难满足这个式子。所以配对的数量越多,越难达到这个条件,有单调性,可以二分。

接着用贪心的思想思考:为了匹配的成功率更高,我们尽量将i指向最小的数字,j指向最大的数字。但是这样会存在浪费:原本我的nums[i]可以和更小的nums[j]匹配,此时如果拿去和最大的nums[j]匹配,这样会使得小的nums[j]更难与其他数字匹配,导致得到的不是最好的结果。

那么我们该如何匹配呢?贪心的总思想是对的,左边数字要尽量小,右边数字要尽量大。我们只需解决这个浪费的问题就行:将最小的k个数和最大的k个数里面,内部相对排名相等的数进行匹配。换成代码语言,就是将nums[i]nums[n−k+i]进行匹配。为啥这样行得通呢?举个反例,假设最小数和最大数全都可以相互匹配,但是如果我拿最小数里面第一小的数去和最大数里面第二小的数匹配,那么最小数里面第二小的数就不一定保证能和最大数里面第一小的数匹配上。从正面比较难解释,但是从反面还是可以解释一下的。基本原理就是避免了“大材小用,结果小材没法大用”所导致的匹配失败。

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        //1.先排序
        sort(nums.begin(),nums.end());
        //2.二分找上下界
        int l=0,r=nums.size()/2,ans=0;
        while (l<=r){
            int mid = l+(r-l)/2;
            bool flag=true;
            for (int i=0;i<mid;i++){
                if (nums[i]*2>nums[nums.size()-mid+i]){ //内部相对排名相等的数进行匹配
                    flag=false;
                    break;
                }
            }
            if (flag){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return ans*2;
    }
};

接着进入困难区域。讲一下第二题:275. H 指数 II,先看题。

在我的个人理解上,判断一个题目能否二分的标准,除了答案是否和某个变量存在单调性之外,还有就是:题目是否方便直接求出答案。这道题目的定义,至少h 篇论文分别被引用了至少 h 次,是非常抽象的一个定义,我几乎想不到能如何直接求出一个答案。但是,我去验证我猜的答案对不对却十分简单:先讲论文引用次数升序排序,假设我猜h=x,那我只需要验证后x篇论文的第一篇的引用次数是否大于等于x就行了。毕竟引用次数是上升的,如果最大的x篇论文的第一篇的引用次数都>=x,那么后面的一定全都符合,这就说明x是合法的。

言归正传,我们来正面推理一下为啥能用二分。先列举一下:如果我至少有4篇论文被引用的次数>=4次,那么我也至少有3篇论文被引用的次数>=3次,也至少有2篇论文被引用的次数>=2次,也至少有1篇论文被引用的次数>=1次,但是却不一定至少有5篇论文被引用的次数>=5次,属于是越小越容易合法的类型,具有单调性,可以二分。

知道这一点后,二分写起来就不难了,甚至不需要写什么遍历的逻辑,一个判断即可。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int l=1,r=citations.size(),ans=0;
        while (l<=r){
            int mid = l+(r-l)/2;
            if (citations[citations.size()-mid]>=mid){ //验证后`x`篇论文的第一篇的引用次数是否大于等于`x`
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return ans;
    }
};

接着来看第三题:2861. 最大合金数,先看题。

看完题后,若有不会,看题解

这题和上一题我判断是否可以二分的“野方法”有异曲同工之妙:如果我要算出最多能制造的金属数量,我得考虑一大堆情况(我没看题解的时候就莫名其妙的朝这个方向去写了),但是如果我猜个答案再去验证其对错,我只需要考虑要用哪台机器做就行了,我此时的花费就可以很简单的正向计算出来,最后看看有没有超出预算就行了。至于到底用哪台机器做,只需要遍历一下就行了,如果全都做不出来就是做不出来,如果有一台能做出来就直接退出,说明这个数量是可行的。

至于单调性,这根本不需要推理,肯定是造的合金越多我的消耗越多,所以是一定有单调性的。

class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        //1.寻找上下界
        long long l=0,minStock=stock[0];
        for (auto x:stock) minStock = min(minStock,(long long)x);
        long long r = budget+minStock,ans=0; // 这里的假设价格为1求上界我是真没想到,太妙了
        //2.二分答案
        while (l<=r){
            long long mid = l+(r-l)/2,sum=0;
            bool flag=false; // 用于其中一台机器满足条件时提前退出,可以帮助循环外的二分框架判断是否符合条件,相当于check函数返回的结果
            for (int i=0;i<composition.size();i++){
                long long totalCost = 0;
                for (int j=0;j<composition[i].size();j++){
                    //先计算对于j种金属的数量需求
                    long long curDemend = composition[i][j]*mid;
                    if (curDemend>stock[j]){
                        totalCost+=(curDemend-stock[j])*cost[j];
                    }
                }
                if (totalCost<=budget){
                    flag=true;
                    break;
                }
            }
            if (flag){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return ans;
    }
};

来看第四题:2071. 你可以安排的最多任务数目,先看题。

如果不会,看题解

正如我上面所说:这题是典型的贪心,用最强的k个工人去做最简单的k个任务,最好不嗑药就能做掉最简单的任务,实在不行要嗑药就做嗑药后能做的最难任务。贪心逻辑好理解,代码实际的实现略有难度。

题解在代码的实现中,十分巧妙的运用了双端队列这个数据结构(c++中是deque,python中是collections.deque,go中只能使用切片模拟)。将一个指针独立外置,然后将嗑药能完成的任务从小到大加入这个队列,退出循环时指针自动就停在了下一次可以开始的位置。如果要嗑药就取出队尾,如果正常弄就取出队首。并且队列可以一直循环使用,只需要一直取队首和队尾就行了,十分的巧妙。如果没想到这个结构(我刚看完题解思路准备去写的时候就没想到这个结构),只能尝试使用遍历等方法,这样不但写起来麻烦,时间复杂度也会上升一个等级。

class Solution {
public:
    bool check(int k,vector<int>& tasks, vector<int>& workers, int pills, int strength){
        int m=workers.size(),j=0;
        deque<int> q;
        for (int i=m-k;i<m;i++){
            //将这个工人能做的所有任务(包括嗑药)加入队列
            while (j<k && tasks[j]<=workers[i]+strength){
                q.push_back(tasks[j]);
                j++;
            }
            if (q.empty()) return false; //在访问队列之前务必检查是否空 如果此处为空 说明这个工人没有能做的任务
            if (q.front()<=workers[i]){ //不嗑药能做最简单的任务
                q.pop_front();
            }else if (pills>0){ //还有剩下的药,那就嗑药
                q.pop_back(); //然后做能做的最难的任务
                pills--;
            }else{
                return false;
            }
        }
        return true;
    }
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        //1.排序
        sort(tasks.begin(),tasks.end());
        sort(workers.begin(),workers.end());
        int l=0,r=min(tasks.size(),workers.size()),ans=0;
        while (l<=r){
            int mid = l+(r-l)/2;
            if (check(mid,tasks,workers,pills,strength)){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return ans;
    }
};

最后,我们来到了地狱难度。第五题:2141. 同时运行 N 台电脑的最长时间,先看题。

如果不会,看题解

这题的核心在于理解题解中当 n⋅x≤sum 成立时,必然可以让 n 台电脑同时运行 x 分钟。这句话。我的语言表达能力并不是很好,在我表达我的看法之前,先让最新的GPT-5帮我解读一下:

这题的核心想法很简单:把“允许换电池”的灵活性,等价成“可以把所有电池的电量像水一样切分并串起来使用”,但注意每块电池在同一时刻只能供给一台电脑。这就引出了一个非常干脆的判定条件。

一、把判定条件说清楚

  • 如果我们打算让 n 台电脑同时运行 x 分钟,那么任何一块电池最多只能贡献 x 分钟(电量超过 x 的部分在这次目标里用不上,相当于被“截断”)。
  • 因此所有电池最多能贡献的总“有效电量”是 sum(min(bi, x))。
  • 想要 n 台电脑各跑 x 分钟,总需求是 n·x。
  • 必要条件:sum(min(bi, x)) ≥ n·x。没有这么多“有效电量”,肯定不可能。

二、为什么这个条件也是充分的(关键点)
把电池按是否 ≥ x 分两类来构造一个可行的调度(只需说明存在性,不要求真的输出过程):

1) 大电池(bi ≥ x)

  • 每块这样的电池可以独立给一台电脑供满 x 分钟。
  • 把它们一一分给不同的电脑,这样“占满”的电脑不再需要其他电池。

2) 小电池(bi < x)

  • 设大电池用了 k 台电脑,还剩 n' = n − k 台电脑没满。
  • 把剩下所有小电池(它们的总和记作 sum')串起来给这 n' 台电脑:给第 1 台从一堆小电池中接一块用完再换下一块,直到累计到 x 分钟;再给第 2 台如法炮制……依次类推。
  • 这种“串电池”的方式不会出现“同一时刻同一电池被两台电脑同时用”的问题,因为每块小电池本身耗尽前持续供电时间 < x,我们可以把任何“一个电池同时贡献给两台电脑”的时间段,向时间轴两端推移为“先贡献给前一台的末尾、再贡献给后一台的开头”,从而避免重叠。
  • 数学上,有 sum' = sum(min(bi, x)) − k·x。由 sum(min(bi, x)) ≥ n·x 可得 sum' ≥ n'·x。小电池总量足以把剩下的 n' 台电脑也各补到 x 分钟。

这就证明了:只要 sum(min(bi, x)) ≥ n·x,就一定能排出一个不同时共享同一电池的调度,让 n 台电脑同时运行 x 分钟。充分性成立。

三、因此可以二分答案

  • 单调性:如果能同时跑 x 分钟,那一定能跑更短的时间,所以“可行时间”关于 x 是单调的。
  • 二分检查:给定 x,检查 sum(min(bi, x)) ≥ n·x 是否成立即可。
  • 边界:

    • 左边界 l=0 一定可行。
    • 右边界 r=⌊sum(batteries)/n⌋+1 一定不可行(因为即使用上全部电量,平均每台也撑不到 r)。
    • 用开区间二分保持不变式:“l 可行,r 不可行”,直到收敛。

四、用样例直观验证

  • 示例1:n=2, batteries=[3,3,3]

    • 试 x=4:sum(min(3,4))*3=9,n·x=8,9≥8 成立,所以 4 可行。
    • 试 x=5:sum(min(3,5))*3=9,n·x=10,不成立,所以 5 不可行。
    • 最大可行是 4。
  • 示例2:n=2, batteries=[1,1,1,1]

    • 试 x=2:sum(min(1,2))*4=4,n·x=4,成立。
    • 试 x=3:sum=4,n·x=6,不成立。
    • 最大可行是 2。

五、实现要点与复杂度

  • 判定函数就是一次线性遍历:累加 min(bi, x),检查是否 ≥ n·x。
  • Python 代码里用 sum(batteries)//n+1 做右边界,二分时每步 O(m),总复杂度 O(m log U),U≈sum/n。
  • 其他语言注意用 64 位整型承载求和与乘法,避免溢出。

六、把题解里“难点句子”翻译成直白话

  • “每个电池的使用时间至多为 min(bi, x)”:因为我们只关心是否能撑到 x 分钟,多出来的电量对这次目标无用,直接“截掉”不影响可行性判断。
  • “小电池串起来供电不会冲突”:因为每块小电池自身供电时长 < x,把它对两台电脑的供电安排成先后相接的时间段即可,不会出现同一时刻一电池供两台电脑。
  • “sum' ≥ n'·x 就能补满剩下的电脑”:既然总小电池量足够,就可以按“用完一块换下一块”的方式逐台凑到 x 分钟。

这就是这道题的核心逻辑:把“换电池”的灵活性抽象为“截断+串接”的可分配模型,判定式 sum(min(bi, x)) ≥ n·x 既必要也充分,从而用二分搜索到最大 x。

它讲的已经非常明白了。我再来一句话概括:这个解法的核心就是,我就用x分钟,那么n台机器需要的总电量就是nx,再将每个电池真正能利用的电量累加起来,如果比它大,那就可以同时运行x分钟。除此之外不管别的。

看懂题解后,其实实行起来不难。因为我只需要计算一个式子,我们讲这么多主要是为了理解为啥这个式子是对的。

class Solution {
public:
    long long maxRunTime(int n, vector<int>& batteries) {
        long long l=1,ave=0;
        for (auto x:batteries) ave+=x;
        ave/=n;
        long long r=ave+1,ans=0;
        while (l<=r){
            long long mid = l+(r-l)/2,sum=0;
            for (auto x:batteries) sum+=min((long long)x,mid); //按照题解的思路来计算有效总电量
            if (mid*n<=sum){ //按照题解的式子来判断
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return ans;
    }
};

5.其他类型题目

最后修改:2025 年 08 月 28 日
如果觉得我的文章对你有用,请随意赞赏