[HOT 100] 2439. 最小化数组中的最大值

1. 题目链接

2439. 最小化数组中的最大值 - 力扣（LeetCode）

2. 题目描述

给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。

每一步操作中，你需要：

• 选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
• 将 nums[i] 减 1 。
• 将 nums[i - 1] 加 1 。

你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。

3. 题目示例

示例 1 :

输入：nums = [3,7,1,6]
输出：5
解释：
一串最优操作是：
1. 选择 i = 1 ，nums 变为 [4,6,1,6] 。
2. 选择 i = 3 ，nums 变为 [4,6,2,5] 。
3. 选择 i = 1 ，nums 变为 [5,5,2,5] 。
nums 中最大值为 5 。无法得到比 5 更小的最大值。
所以我们返回 5 。

示例 2 :

输入：nums = [10,1]
输出：10
解释：
最优解是不改动 nums ，10 是最大值，所以返回 10 。

4. 解题思路

1. 二分查找确定候选值
   • 最小可能值是0，最大可能值是数组的初始最大值。通过二分法逐步缩小范围，找到满足条件的最小最大值。
2. 验证函数 (**check**)
   • 从后向前遍历数组，计算每个元素在给定候选值 limit 下是否需要转移多余的值到前一个元素。若所有元素最终能被调整到不超过 limit，则候选值可行。

5. 题解代码

class Solution {
    public int minimizeArrayValue(int[] nums) {
        int left = -1, right = 0;
        // 初始化右边界为数组最大值
        for (int x : nums) right = Math.max(right, x);
        
        // 二分查找：找到最小的可行最大值
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (check(nums, mid)) {
                right = mid; // 可行，尝试更小的值
            } else {
                left = mid;  // 不可行，增大下界
            }
        }
        return right; // 最终 right 是最小可行最大值
    }

    // 验证函数：判断是否所有元素可调整到不超过 limit
    private boolean check(int[] nums, int limit) {
        long extra = 0; // 记录需要向前转移的“多余量”
        for (int i = nums.length - 1; i > 0; i--) {
            // 当前元素值加上之前的转移量，若超过 limit，则计算新的转移量
            extra = Math.max(nums[i] + extra - limit, 0);
        }
        // 最终检查第一个元素是否能容纳所有转移量
        return nums[0] + extra <= limit;
    }
}

6. 复杂度分析

• 时间复杂度：O(n)，其中n为nums的长度。
• 空间复杂度：O(1)，仅用到若干变量。