最小化数组中的最大值

2023-12-21 17:46:20

说在前面

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

题目描述

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

文章来源:https://blog.csdn.net/Twinkle_sone/article/details/135134221
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。