Medium

题目描述

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

每次操作中，你必须：

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

返回执行任意次操作后，nums 中 最大值 的 最小可能值 。

示例 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
解释：
最优方案是不执行任何操作，10 已经是最大值。
因此，返回 10 。

提示：

  • n == nums.length
  • 2 <= n <= 10^5
  • 0 <= nums[i] <= 10^9

解题思路

这个问题的核心思路是：我们只能将右边的元素值转移到左边，不能反向操作。因此，对于任意位置 i，它能获得的最大值受到从位置 0 到 i 的前缀和的限制。

方法一：贪心算法（推荐） 关键观察：对于位置 i，如果我们想让数组的最大值尽可能小，那么前 i+1 个元素应该尽可能平均分配。假设前 i+1 个元素的和为 sum，那么最优情况下每个位置的值约为 sum/(i+1)。但由于只能向左转移，位置 i 的最小可能值是 ⌈sum/(i+1)⌉。

我们从左到右遍历数组，维护前缀和，计算每个位置能达到的最小最大值，取所有位置的最大值即为答案。

方法二：二分搜索 我们可以二分搜索答案。对于每个候选答案 mid，检查是否能通过操作使得数组的最大值不超过 mid。检查时从右往左遍历，贪心地将超过 mid 的部分转移到左边。

时间复杂度上，贪心方法更优，代码也更简洁，因此推荐使用贪心方法。

代码实现

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        long long sum = 0;
        int result = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            result = max(result, (int)((sum + i) / (i + 1)));
        }
        
        return result;
    }
};

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        total = 0
        result = 0
        
        for i, num in enumerate(nums):
            total += num
            result = max(result, (total + i) // (i + 1))
        
        return result

public class Solution {
    public int MinimizeArrayValue(int[] nums) {
        long sum = 0;
        int result = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            sum += nums[i];
            result = Math.Max(result, (int)((sum + i) / (i + 1)));
        }
        
        return result;
    }
}

var minimizeArrayValue = function(nums) {
    let sum = 0;
    let result = 0;
    
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        result = Math.max(result, Math.ceil(sum / (i + 1)));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度贪心算法二分搜索
时间复杂度O(n)O(n log(max(nums)))
空间复杂度O(1)O(1)

相关题目