最小化数组中的最大值

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

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

每一步操作中，你需要：

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

将 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
解释：
最优解是不改动 nums ，10 是最大值，所以返回 10 。

提示：

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

思路分析

首先我们要先理解一下题目的意思，题目会给我们一个数组，我们可以选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。将 nums[i] 减 1 ，同时将 nums[i - 1] 加 1 。我们可以执行任意次操作，需要我们计算操作后可以得到的 nums 数组中 最大值 最小 为多少。

了解了题意之后，我们可以知道我们要尽可能将数组数值平均，但同时我们只能对进行减一操作的左边的数字进行加一，也就是说一个位置减掉的值只能移动到其左侧任一位置的数字加上，我们可以以示例1nums = [3,7,1,6]来分析一下。

我们可以对连续的子数组进行求平均值：

• [3] 平均值为3
• [3,7]平均值为5，平均值大于上一数组平均值，说明当前位置的数字可以将其自身的数字往左边移
• [3,7,1]平均值为11/3,平均值小于上一数组的平均值，说明当前位置无法得到更大的值，因此最小的最大值只能取得前面求得的平均值最大值5
• [3,7,1,6]平均值为17/4，当前平均值小于5，因此也无法获得更大的最大值。

所以最后得到的答案为5。

我们每次只需要计算连续数组的平均值，取得最大的值即为我们所需要的答案。

完整AC代码如下：

AC代码

/**
 * @param {number[]} nums
 * @return {number}
 */
 var minimizeArrayValue = function(nums) {
    let sum = 0;
    let ans = 0;
    for(let i = 0; i < nums.length; i++){
        sum += nums[i];
        ans = Math.max(ans, sum / (i + 1));
    }
    return Math.ceil(ans);
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。