二分答案：最小化最大值问题

当题目要求"最小化最大值"或"最大化最小值"时，可以二分答案，配合 check 函数验证可行性。

分割数组的最大值（LeetCode 410）

将数组分成 m 个非空且连续的子数组，使各子数组和的最大值最小。

public int splitArray(int[] nums, int m) {
    int lo = Arrays.stream(nums).max().getAsInt();  // 单个元素最大值
    int hi = Arrays.stream(nums).sum();             // 整个数组之和
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canSplit(nums, m, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

// 判断在最大子数组和 ≤ maxSum 的前提下能否分成 ≤ m 段
private boolean canSplit(int[] nums, int m, int maxSum) {
    int count = 1, curr = 0;
    for (int num : nums) {
        if (curr + num > maxSum) { count++; curr = 0; }
        curr += num;
    }
    return count <= m;
}

最小化最大值（LeetCode 2064）

将 n 个数分配给 n 行，每行对应一个分组大小，使最大值最小。（同类问题均用此模板）

通用模板：

lo = 最小可能答案
hi = 最大可能答案
while lo < hi:
    mid = (lo + hi) / 2
    if check(mid):   # mid 是可行的？
        hi = mid     # 尝试更小
    else:
        lo = mid + 1 # mid 太小，增大
return lo

爱吃香蕉的珂珂（LeetCode 875）

（前面已讲，这里给出最精简版）

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 1;
    for (int p : piles) hi = Math.max(hi, p);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        long hours = 0;
        for (int p : piles) hours += (p + mid - 1) / mid;
        if (hours <= h) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

在 D 天内送达包裹的能力（LeetCode 1011）

（前面已讲，给出最精简版）

public int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) { lo = Math.max(lo, w); hi += w; }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int d = 1, curr = 0;
        for (int w : weights) {
            if (curr + w > mid) { d++; curr = 0; }
            curr += w;
        }
        if (d <= days) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

制作 m 束花所需的最少天数（LeetCode 1482）

public int minDays(int[] bloomDay, int m, int k) {
    if ((long) m * k > bloomDay.length) return -1;
    int lo = 1, hi = Arrays.stream(bloomDay).max().getAsInt();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canMake(bloomDay, m, k, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

private boolean canMake(int[] bloomDay, int m, int k, int day) {
    int bouquets = 0, flowers = 0;
    for (int d : bloomDay) {
        if (d <= day) {
            flowers++;
            if (flowers == k) { bouquets++; flowers = 0; }
        } else {
            flowers = 0;
        }
    }
    return bouquets >= m;
}

总结：答案型二分的判断