躬行算法之最小的最大值

最近看到这样一道面试题，求最小的最大值，觉得挺有意思，在这里分享下。

描述

给定一个数组 a，包含 n 个整数。再给定一个整数 k，可以给数据中任意整数加 1，总共可以加 k 次。加完 k 次之后，找出数组中的最大数，要求得到最小的最大数。

解析

乍一看，甚至题目都没读懂。啥，最大数，还最小？这道题最关键的也就是理解题目的含义，

有一种理解，我认为非常贴近生活，就是把数组 a 理解为若干个垃圾桶，这些垃圾桶中有数量不等的垃圾，而此时我们手里有 k 袋垃圾，可以任意投放。放在这个题目中，就是要找到合理的投放方式使得垃圾桶尽可能不要堆得太高，然后找到最满的桶中的垃圾数量。

这样一考虑，题目就变得非常简单了。

回到题目，首先计算出数组 a 中最大数为 max，尝试把所有小于 max 的数填平。若 k 值太小，无法填平，则最小的最大数即为 max；若 k 值够大，填平之后 k 还有剩余，则依次平铺，每一轮每个元素都加 1，直到 k 归零为止。

答案

根据以上分析，很容易写出以下答案：

private int findMinMaxValue(int[] array, int k) {
    int n = array.length, max = 0, sum = 0;
    for (int x : array) {
        max = Math.max(x, max);
        sum += x;
    }
    return k + sum <= n * max ? max : (k + sum + n - 1) / n; // (k+sum+n-1)/n 相当于 (k+sum)/n 向上取整
}