您的位置:首页 > 教育 > 锐评 > 制作asp手机网站_武汉市人民政府领导分工_百度指数下载手机版_中山百度seo排名公司

制作asp手机网站_武汉市人民政府领导分工_百度指数下载手机版_中山百度seo排名公司

2025/4/4 14:23:04 来源:https://blog.csdn.net/Teriri_/article/details/143075510  浏览:    关键词:制作asp手机网站_武汉市人民政府领导分工_百度指数下载手机版_中山百度seo排名公司
制作asp手机网站_武汉市人民政府领导分工_百度指数下载手机版_中山百度seo排名公司

2439. 最小化数组中的最大值

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

每一步操作中,你需要:

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

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

最小化数组中的最大值 碰到这个关键词,就需要想到 二分查找,我们先一步一步来讲:

前缀和遍历

这道题的核心在于最小化数组中的最大值,并且操作只能将元素的值从右向左(<-)移动。这意味着我们只能减小右边的元素,增加左边的元素,无法将值从左向右移动。

为了解决这个问题,我们需要找到一个方法,使得在移动元素的过程中,数组的最大值被最小化

具体步骤:

1. 前缀和与平均值:

  • 前缀和(Prefix Sum): 计算数组从开始到当前位置的累加和 prefixSum
  • 平均值: 计算当前前缀和除以元素数量的平均值,并取向上取整,因为数组元素是整数,不能有小数。
  • 这里的平均数就是前 i 个数的最小化最大值。

2. 维护最大平均值:

  • 在遍历数组的过程中,维护一个全局的最大平均值,这个值就是我们所求的最小最大值。

原因分析:

  • 平衡数组元素: 我们希望在不违反操作规则的情况下,使数组元素尽可能均衡。
  • 限制条件: 由于只能将值从右向左移动,左边的元素只能变大或保持不变,不能变小。
  • 最小化最大值: 通过计算平均值,我们确保左边的元素不会因为过度增加而导致新的最大值。

为什么要每次都更新最大值,而不是直接使用(sum + n - 1) / (n) 计算结果?

通过一个具体的例子来理解这个问题。

示例数组:

nums=[10,1,1,1,1]

  • 数组长度:n = 5
  • 总和:sum = 14

使用公式得到 (sum + n − 1) / n = 3,得到的最小最大值是 3。这显然不合理,我们是无法通过操作将数组的最大值降低到 3 的,在数组的某些位置,可能会出现局部的“瓶颈”,直接使用全局平均值可能无法满足某些位置的最大值限制,result = max(result, avg);就是记录这一瓶颈的过程。

完整代码:

class Solution {
public:int minimizeArrayValue(vector<int>& nums) {long long prefixSum = 0;    // 前缀和int result = 0;int n = nums.size();for (int i = 0; i < n; ++i) {prefixSum += nums[i];int avg = (prefixSum + i) / (i + 1); // 前i个数的最小化最大值result = max(result, avg);}return result;}
};

二分查找

首先,确定最小化最大值的范围肯定位于区间 [nums.min(), nums.max()] 范围内,我们在这个范围内选择一个数 x,然后判定能否让这个数组的元素都小于等于 x

  • 如果可以,则对于 y∈(x, nums.max()],肯定也都是可以的,那我们接下来只需要在[nums.min(), x) 这个范围里继续寻找。
  • 如果不可以,那么我们就在(x, nums.max()]这个范围里寻找。

这就很像二分查找的思路了。

二分查找的核心思想:

  • 目标: 在一个范围内搜索可能的最小最大值 x,使得通过操作,可以将数组中的所有元素调整到不超过 x
  • 方法: 使用二分查找,从可能的最小值到可能的最大值之间搜索,判断对于某个中间值 mid,是否可以通过操作将数组调整到不超过 mid
  • 判定条件: 设计一个判定函数 check(mid, nums),判断对于给定的 mid,能否通过操作使数组中所有元素都不超过 mid

这里的 mid,就是我们猜测的最小化最大值。

算法步骤:

1. 确定二分查找的范围:

        左边界 left 数组元素的最小值, left = *min_element(nums.begin(), nums.end());

        右边界 right 数组元素的最大值,right = *max_element(nums.begin(), nums.end());

2. 二分查找:

        当 left <= right 时,执行以下步骤:

                a. 计算中间值 mid = left + (right - left) / 2

                b. 调用判定函数 check(mid, nums)

                        如果返回 true,表示可以将数组调整到不超过 mid,则更新 right = mid - 1,继续找是否有更小的 mid

                        如果返回 false,表示无法调整到不超过 mid,则更新 left = mid + 1,继续找是否有更大的 mid

3. 返回结果:

最终 left 即为数组可以调整到的最小最大值。

为什么二分查找有效:

  • 操作的单调性: 对于较小的 mid,可能无法将数组调整到不超过 mid;对于较大的 mid,一定可以调整。
  • 判定函数的单调性:mid 递增时,判定函数从 false 变为 true,且一旦为 true,后续更大的 mid 一定也是 true
  • 因此,二分查找可以有效地找到最小的满足条件的 mid 值。

完整代码:

class Solution {
public:bool check(int mid, vector<int>& nums) {long long need = 0;   // 记录需要nums[i-1]需要向左移动的值,初始化为0for (int i = nums.size() - 1; i >=0; --i) {long long total = nums[i] + need; // nums[i]的实际值,等于nums[i-1]需要向左移动的值 + nums[i]的值if (total > mid) {// 如果nums[i]的实际值 > mid,需要继续向左移动need = total - mid;} else {need = 0;}}return (need == 0);}int minimizeArrayValue(vector<int>& nums) {long long left = *min_element(nums.begin(), nums.end());long long right = *max_element(nums.begin(), nums.end());while (left <= right) {long long mid = left + (right - left) / 2;if (check(mid, nums)) {right = mid - 1;} else {left = mid + 1;}}return left;}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com