2439.md

Minimize Maximum of Array

题目

You are given a 0-indexed array nums comprising of n non-negative integers.

In one operation, you must:

Choose an integer i such that 1 <= i < n and nums[i] > 0. Decrease nums[i] by 1. Increase nums[i - 1] by 1. Return the minimum possible value of the maximum integer of nums after performing any number of operations.

Example 1:
Input: nums = [3,7,1,6]
Output: 5
Explanation:
One set of optimal operations is as follows:
1. Choose i = 1, and nums becomes [4,6,1,6].
2. Choose i = 3, and nums becomes [4,6,2,5].
3. Choose i = 1, and nums becomes [5,5,2,5].
The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5.
Therefore, we return 5.

Example 2:
Input: nums = [10,1]
Output: 10
Explanation:
It is optimal to leave nums as is, and since 10 is the maximum value, we return 10.
 

Constraints:

n == nums.length
2 <= n <= 105
0 <= nums[i] <= 109

思路

题目解读
题中的operation是有传递性的，对于nums[i]做decrese(n) 可推断出任何nums[i-x]做increse(n) 其中i-x>=0
而且只能从右往左传递，也就是说对于case[100,1]这种情况，100是没法摊一些值到右边的。
所以可以这么理解 题中的maximun就是水位，水位没填完前可以一直填，填完后升一格继续填水。

针对case：[1,7,3,6]
处理1时：水位max=1，实际填充水为sum=1，最大可填充sumMax=1，剩余可填充left=0，桶数为1
处理7时：水位max=4，实际填充水为sum=8，最大可填充sumMax=8，剩余可填充left=0，桶数为2
处理3时：水位max=4，实际填充水为sum=11，最大可填充sumMax=12，剩余可填充left=1，桶数为3
处理6时：水位max=5，实际填充水为sum=17，最大可填充sumMax=20，剩余可填充left=3，桶数为4

所以结果为5

代码

func minimizeArrayValue(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	max, sumMax, sum := nums[0],nums[0],nums[0]
	left := 0
	for i := 1; i < len(nums); i++ {
		curNum := nums[i]
		sum += nums[i]
		if curNum - left <= max {
			sumMax += max
			left = sumMax - sum
			continue
		}
		if curNum - left > max {
			newMax := sum / (i + 1)
			if newMax * (i+1) < sum {
				newMax += 1
			}
			max = newMax
			sumMax = max * (i+1)
			left = sumMax - sum
		}
	}
	return max
}

暴力解，直接实际改动数组，通过率64/68

func minimizeArrayValue(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	max := nums[0]
	minIndex := 0
	for i := 1; i < len(nums); i++ {
		//fmt.Printf("NUMS: %+v\n", nums)
		num := nums[i]
		if num < max && minIndex == 0 {
			minIndex = i
			continue
		}
		if num == max && minIndex == 0 {
			continue
		}
		if num >= max && minIndex == 0 {
			sum := num + max*i
			newMax := sum / (i + 1)
			left := sum % newMax
			if left != 0 {
				max = newMax + 1
			} else {
				max = newMax
			}
			for j := 0; j <= i; j++ {
				left--
				if left >= 0 {
					nums[j] = newMax + 1
					continue
				}
				if left == -1 {
					minIndex = j
				}
				nums[j] = newMax
			}
			continue
		}
		curIndex := i
		for num >= max && minIndex != 0 {
			num = num - (max - nums[minIndex])
			nums[minIndex] = max
			minIndex++
			if minIndex == i && num >= max {
				i--
				minIndex = 0
				break
			}
		}
		nums[curIndex] = num
	}
	//fmt.Printf("NUMS: %+v\n", nums)
	//fmt.Printf("MAX: %+v", max)
	return max
}