【二分答案法】Leetcode相关题目解析

题目：162. 寻找峰值 - 力扣（LeetCode）

题目描述：

????????

题目分析：

? ? ? ? （1）据题知，索引-1、索引n（n为数组长度）处的元素都默认为无穷小，我们可以在一开始特判一些简单情况：当数组长度等于1时，直接返回0；当索引0处的元素大于索引1处的元素时，直接返回0；当索引n - 1处的元素大于索引n-2处的元素时，返回n - 1。

? ? ? ? （2）如果给定的数组不满足特判条件，用折线来描述这个数组的升降，一定能找到一个峰值元素，如下图所示。

? ? ? ? 索引0到索引1是上升趋势，索引n-2到索引n-1是下降趋势，由于数组不存在重复元素，所以无论你怎么拼接这条折线，中间一定有一个峰值元素。

? ? ? ? （3）假设我们二分到一个元素nums[m]，有三种情况：1、nums[m]就是峰值元素，更新答案，退出循环；2、nums[m-1] > nums[m]，这里呈下降趋势，而索引0到索引1是上升趋势，所以在0 到?m - 1这个区间肯定有一个峰值元素，right?= m - 1往左侧二分；3、nums[m+1] > nums[m]，这里呈上升趋势，而索引n - 2到索引n - 1是下降趋势，所以在m + 1 到 n - 2这个区间肯定有一个峰值元素，left = m + 1往右侧二分。

Code：

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        
        //数组中只有一个元素，直接返回0
        if(n == 1)
        return 0;
        
        //索引0处的元素满足要求，返回0
        if(nums[0] > nums[1])
        return 0;
        
        //索引n - 1处的元素满足要求，返回n - 1
        if(nums[n - 1] > nums[n - 2])
        return n - 1;

        int left = 1,right = n - 2;
        int ans = 0;
        while(left <= right){
            int m = left + (right - left) / 2;
            
            //nums[m-1] > nums[m]，这里是下降趋势
            //那么答案一定在左侧，往左侧二分
            if(nums[m - 1] > nums[m]){
                right = m - 1;
            }
            //nums[m+1] > nums[m]，这里是上升趋势
            //答案一定在右侧，往右侧二分
            else if(nums[m + 1] > nums[m]){
                left = left + 1;
            }else{
                //nums[m+1]和nums[m-1]都不大于nums[m]
                //那么nums[m]就是峰值元素
                ans = m;
                break;
            }
        }
        return ans;
    }
}

题目：875. 爱吃香蕉的珂珂 - 力扣（LeetCode）

题目描述：

题目分析：

? ? ? ? （1）题目给你piles.length堆香蕉，第i堆香蕉的数量为piles[i]，如果珂珂吃香蕉的速度k（单位是小时）大于香蕉数piles[i]，吃完她会停下休息；如果速度k等于piles[i]，吃完她不会休息会继续吃下一堆香蕉；如果速度k小于piles[i]，比如k = 2，piles[i] = 7，她吃完这堆香蕉需要4小时，因为每次吃完香蕉如果还有剩余时间她会选择休息。

? ? ? ? （2）题目给定的堆数piles.length小于管理员离开的时间h，意味着珂珂总能以一个速度k在管理员回来之前吃完所有香蕉。同时piles[i] >= 1，表示每堆香蕉至少有一根香蕉。

? ? ? ? （3）分析完题目，我们来预估答案的范围。答案最小可以是1，因为piles数组可能是这种形式：[1,1,1,1,1]；答案最大不会超过最大香蕉数，假设piles为：[2,3,5,100,79]，最大香蕉数是100，如果管理员离开的时间是5（不会小于香蕉堆数），那么此时珂珂吃香蕉的速度必须大于等于100才有可能在管理员回来之前吃完所有香蕉。101、102……等速度虽然也能在规定时间内吃完所有香蕉，但不符合题目要求的最小速度。

? ? ? ? （4）如果珂珂能以速度k在规定时间内吃完香蕉，那么她以速度k + 1、k + 2肯定也能在规定时间内吃完所有香蕉，此时我们往左侧二分寻找更小的速度（速度满足要求，要寻找更小的速度）；如果珂珂以速度k不能在规定时间内吃完香蕉，那么她以速度k - 1、k - 2肯定也无法在规定时间内吃完所有香蕉，此时我们往右侧二分寻找符合要求的答案（速度不满足要求，要满足要求的速度）。

Code：

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;

        //答案范围在：[1,最大香蕉数]之间
        int left = 1,right = 0;

        for(int pile : piles)
        right = Math.max(pile,right);

        int ans = 0;
        while(left <= right){
            int m = left + (right - left) / 2;

            //如果以速度m能在规定时间内吃完香蕉
            //那么以比m大的速度吃香蕉，肯定也能在规定时间内吃完
            if(prove(m,piles,h)){
                //记录答案，并往左侧二分
                right = m - 1;
                ans = m;
            }else{
                //否则往右侧二分
                left = m + 1;
            }
        }
        return ans;
    }

    private boolean prove(int speed,int [] piles,int h){
        //由于piles[i] <= 10^，防止整型溢出，用long
        long hour = 0;

        for(int pile : piles){
          //如果速度大于等于香蕉数，那么只需要1小时足以
          if(speed >= pile)
          hour++;
          //如果速度小于香蕉数，则需要(pile / speed)向上取整
          else
          hour += (pile + speed - 1) / speed;//这里是向上取整的写法
        }
        //最后判断以速度speed吃香蕉，是否能在规定时间内吃完
        return hour <= h;
    }
}

题目：410. 分割数组的最大值 - 力扣（LeetCode）

题目描述：

题目分析：

? ? ? ? （1）题目给定一个非负整数数组nums和一个整数k，要求将数组nums分成k个连续子数组，使得这k个子数组和的最大值最小。

? ? ? ? （2）将题目抽象成画家问题：给你一个整数数组nums，nums[i]代表画第i副画所需要的时间，同时给你k个画家并行作画，每个画家只能画连续的画（不能nums[i]、nums[i + 2]这样跳跃式的作画），问如果画家同时作画，如何分配画家能使得画完所有画所需的时间最少。

? ? ? ? 图解：

? ? ? ? （3）来预估答案的范围，答案最小可能是0，因为题目提示：nums[i] >= 0，nums数组有可能是：[0,0,0,0,...]这种形式；答案最大可能是数组总和，有可能题目给定k = 1，只有一个画家，那么他画完所有画需要的时间就是数组总和。

? ? ? ? （4）定义一个验证函数prove(int [ ] nums,int value)，函数定义：将nums数组拆分成多个子数组，要求每个子数组的和 <= value，返回子数组个数。在使用二分前先来达成一个共识：value越大，子数组能容纳的元素越多，能拆分nums数组得到的子数组个数就越少；value越小，子数组能容纳的元素越少，能拆分nums数组得到的子数组个数就越多。

? ? ? ? （5）基于上述共识，如果一个值value能拆分的子数组个数 <= k（题目要求的子数组个数），那么比value大的数能拆分的子数组个数肯定也 <= k；如果一个值value能拆分的子数组个数 > k，那么比value小的数能拆分的子数组个数肯定也 > k。

Code：

class Solution {
    public int splitArray(int[] nums, int k) {

        //答案范围：[0,数组总和]
        int left = 0,right = 0;

        for(int n : nums)
        right += n;

        int ans = 0;
        while(left <= right){
            int m = left + (right - left) / 2;

            //如果分得的子数组个数<=k
            if(prove(nums,m) <= k){
                
                //满足题目要求，更新答案
                //并往左侧二分，看有没有更小的值符合要求
                ans = m;
                right = m - 1;
            }else{
                //如果子数组个数 > k
                //不符合题目要求，往右侧二分，寻找满足要求的答案
                left = m + 1;
            }
        }
            return ans;
    }
    
    //函数定义：将nums数组拆分成多个子数组，要求每个子数组的和<=value，返回子数组个数
    //如果拆分不了就返回整型最大值
    public int prove(int [] nums,int value){
        //bucket变量代表子数组个数
        int bucket = 1;
        int sum = 0;

        for(int num : nums){
            //元素值num > value，拆分不了
            if(num > value){
                return Integer.MAX_VALUE;
            }
            
            //往子数组中纳入元素
            sum += num;
            //发现子数组和 > value时
            if(sum > value){
                //bucket++，并让sum从当前元素开始累加，代表生成一个新的子数组
                bucket++;
                sum = num;
            }
        }
        return bucket;
    }
}