二分题目leetcode

总结来说，如果发现题目中存在单调关系，就可以尝试使用二分搜索的思路来解决。

爱吃香蕉的珂珂

题目链接

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxBound=0;
        int sz=piles.length;
        for(int i=0;i<sz;i++){
            maxBound=Math.max(maxBound,piles[i]);
        }
        int left=1,right=maxBound;
        while(left<right){
            int mid=(left+right)/2;
            if(needTimes(mid,piles)<=h){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    //以速度 k 根/小时，返回吃完所有香蕉需要的时间
    int needTimes(int k,int[]piles){
         int sz=piles.length;
         int times=0;
         for(int i=0;i<sz;i++){
            if(piles[i]<=k){//一个小时之内吃完
                times++;
            }else{
                int divi=piles[i]/k;
                if(piles[i]%k==0){
                     times+=divi;
                }else{
                    times+=(divi+1);
                }
            }
          
         }
         return times;
    }
}

在D天内送达包裹的能力

题目链接

分割数组的最大值

题目链接

class Solution {
    //这么想，nums是包裹，k为船的数量，目的是运完所以货，让你求船的最小运载能力
    public int splitArray(int[] nums, int k) {
        int maxVal=0;
        int sum=0;
        int sz=nums.length;
        for(int i=0;i<sz;i++){
            sum+=nums[i];
            maxVal=Math.max(maxVal,nums[i]);
        }
        int left=maxVal,right=sum;
        while(left<right){
            int mid=(left+right)/2;
            if(needK(mid,nums)<=k){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    //返回需要 几个船 可以运完货
    int needK(int maxCapacity,int[]nums){
        int sz=nums.length;
        int left=0,right=0;
        int windowSum=0;
        int ships=0;
        while(right<sz){
            //扩大窗口
            windowSum+=nums[right++];
            //检查什么时候停止上货
            if(right<sz && windowSum+nums[right]>maxCapacity){
                //如果加上下一个包裹就超载了，停止上货
                ships++;
                windowSum=0;
                left=right;
            }
        }
        ships++;
        return ships;
    }
}