首先，我们可以明确最低运载能力必须要不小于数组中的最大值（必须要满足一天至少运一个，运载能力至少要比每个包裹的重量都要大才行，不然就会出现有包裹一直运不走），不大于数组的总和（一天全部运走），即区间[max(weights), sum(weights)];

那么我们怎么判断运载能力为值H的时候能满足在D天內送达呢？见函数verification：

1、判断最低运载能力为H的时候能否在D天内送达

  1. //判断最低运载能力为H的时候能否在D天内送达
  2. public boolean verification(int[] weights, int D, int H){
  3.     //天数计数，初始化为1
  4.     int count = 1;
  5.     //每天的包裹总量
  6.     int singleWeight = 0;
  7.     for(int i = 0; i < weights.length; ++i){
  8.         //累计包裹总量
  9.         singleWeight += weights[i];
  10.         //如果累计包裹总量singleWeight > H，天数+1
  11.         if(singleWeight > H){
  12.             ++count;
  13.             singleWeight = weights[i];
  14.         }
  15.         //如果当前累计的天数count > D，说明当前H不满足条件，返回false
  16.         if(count > D){
  17.             return false;
  18.         }
  19.     }
  20.     //说明当前H满足条件，返回true
  21.     return true;
  22. }

2、区间[max(weights), sum(weights)]内满足函数verification的值都可以作为最低运载能力的候选值，但是我们求满足条件中的最小值，这里我们采用二分法查找

  1. //二分法查找满足条件中的最小值
  2. public int shipWithinDays(int[] weights, int D) {
  3.     //二分查找 r = 数组的总和， l = 数组的最大值
  4.     int r = Arrays.stream(weights).sum();
  5.     int l = Arrays.stream(weights).max().getAsInt();
  6.     //l < r
  7.     while(l < r){
  8.         //取中间值
  9.         int mid = (l + r) >> 1;
  10.         //如果mid满足verification，则逼近右指针
  11.         if(verification(weights, D, mid)){
  12.             //包括mid
  13.             r = mid;
  14.         }else{
  15.             //逼近左指针，mid + 1
  16.             l = mid + 1;
  17.         }
  18.     }
  19.     //返回当前l就是最小的满足条件的值，即最低运载能力
  20.     return l;
  21. }

代码：

  1. class Solution {
  2.     //判断最低运载能力为H的时候能否在D天内送达
  3.     public boolean verification(int[] weights, int D, int H){
  4.         //天数计数，初始化为1
  5.         int count = 1;
  6.         //每天的包裹总量
  7.         int singleWeight = 0;
  8.         for(int i = 0; i < weights.length; ++i){
  9.             //累计包裹总量
  10.             singleWeight += weights[i];
  11.             //如果累计包裹总量singleWeight > H，天数+1
  12.             if(singleWeight > H){
  13.                 ++count;
  14.                 singleWeight = weights[i];
  15.             }
  16.             //如果当前累计的天数count > D，说明当前H不满足条件，返回false
  17.             if(count > D){
  18.                 return false;
  19.             }
  20.         }
  21.         //说明当前H满足条件，返回true
  22.         return true;
  23.     }
  24.     //从数组的最大元素开始遍历判断值i是否满足verification
  25.     public int shipWithinDays(int[] weights, int D) {
  26.         //二分查找 r = 数组的总和， l = 数组的最大值
  27.         int r = Arrays.stream(weights).sum();
  28.         int l = Arrays.stream(weights).max().getAsInt();
  29.         //l < r
  30.         while(l < r){
  31.             //取中间值
  32.             int mid = (l + r) >> 1;
  33.             //如果mid满足verification，则逼近右指针
  34.             if(verification(weights, D, mid)){
  35.                 //包括mid
  36.                 r = mid;
  37.             }else{
  38.                 //逼近左指针，mid + 1
  39.                 l = mid + 1;
  40.             }
  41.         }
  42.         //返回当前l就是最小的满足条件的值，即最低运载能力
  43.         return l;
  44.     }
  45. }

其他「二分」相关题解

二分模板

  1. 两数相除 : 二分 + 倍增乘法解法（含模板）

二分本质 & 恢复二段性处理

  1. 搜索旋转排序数组（找目标值） : 严格 O(logN)，一起看清二分的本质

  2. 搜索旋转排序数组 II（找目标值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质

  3. 寻找旋转排序数组中的最小值（找最小值） : 严格 O(logN)，一起看清二分的本质

  4. 寻找旋转排序数组中的最小值 II（找最小值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质

二分 check 函数如何确定

  1. 在排序数组中查找元素的第一个和最后一个位置 : 考察对「二分」的理解，以及 check 函数的「大于 小于」怎么写

未消化：

1.取中间值用>>?
//取中间值 int mid = (l + r) >> 1;
2.取最大值？？
int l = Arrays.stream(weights).max().getAsInt();

1.Java中的>>，>>>
2.Java 8 Stream