2439. 最小化数组中的最大值-暴力解法+动态规划法

2439. 最小化数组中的最大值-暴力解法+动态规划法

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

每一步操作中，你需要：

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

你可以对数组执行 任意 次上述操作，请你返回可以得到的 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 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimize-maximum-of-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力解法其实思想很简单，很多同学应该都能想到：

int minimizeArrayValue(int* nums, int numsSize){
   bool r=true;
   while(r){
       r=false;

        for(int i=1;i<numsSize;i++){

            if(nums[i]-nums[i-1]>=1){
                r=true;
                nums[i]--;
                nums[i-1]++;
            }
            
        }
      
    }
    int max=0;
      for(int i=0;i<numsSize;i++){
          max=fmax(max,nums[i]);
         printf("%d ",nums[i]);
     }
     
    return max;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

动态规划算法可能比较特别，对于这一题，解题思路如下：
对于一个数组 a[0,numsize-1] 。
1.首先我们维护一个平均值，对一个数组其区间【0,b】中的数值平均值位mid时，当新加入一个小于平均值的数时，那么我们知道【0,b】中一定有一个值大于mid的值，【0，b】的最大值是不会被减小的，所以结果不变。

2.当新加入一个等于平均值时，我们结果肯定即使也是【0，b】中的最大值了

3.当新加入一个大于平均值的数时，可知，该数是可以向【0，b】数组增量，自己减少，但是我们知道，数组的最大同通量一定也是加入的数 val-减去平均值mid，其次，输入那么多的同时如果【0，b】中的数存在的最大值大于mid的话，那么结果还是不变的，最大值肯定还是那个值。
综上，解题代码如下

int minimizeArrayValue(int* nums, int numsSize){
    long long max=nums[0],sum=nums[0];
    for(int i=1;i<numsSize;i++){
        sum=sum+nums[i];
        //printf("%d %d ",sum/(i+1),sum%(i+1)?1:0);
        max=fmax(max,sum/(i+1)+(sum%(i+1)?1:0));

    }

    return max;

}
1
2
3
4
5
6
7
8
9
10
11
12