难度: Medium
给你一个下标从 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.length2 <= n <= 1050 <= nums[i] <= 109运行时间: 103 ms
内存: 25.7 MB
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
return max((s + i) // (i + 1) for i, s in enumerate(accumulate(nums)))
题解采用了前缀和和数学分析的方法。首先，通过遍历并累计数组的和，构造一个前缀和数组。接着，对于每个前缀和，计算其与当前索引的商，这个商代表如果从数组的开始到当前索引的数全部平均分配时，能够达到的最大平均值。这个最大平均值实际上代表了经过一系列操作后，数组中可能达到的最大值的一个下界。因此，最终的结果是所有这些商的最大值，即在所有可能的情况下，数组中最大值的最小可能值。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
# 使用accumulate计算前缀和
from itertools import accumulate
# max函数用于计算所有前缀和与索引商的最大值
return max((s + i) // (i + 1) for i, s in enumerate(accumulate(nums)))
选择使用前缀和和数学分析方法是因为这种方法可以直接通过数学途径快速求解最优解，而不需要构建复杂的状态转移方程或进行迭代选择。前缀和可以快速计算任意前缀区间的和，从而能够高效地评估分配策略下的可能最大值。此外，数学分析方法通过直接计算每个前缀的平均值并取整，可以直接得到使得数组最大值最小的可能值，这种方法简洁且效率高。动态规划或贪心算法在此问题中可能需要更多的计算和复杂的逻辑，而前缀和和数学分析提供了一种更直接和计算效率更高的解决方案。
在计算每个前缀和与当前索引的商时使用整数除法是因为题目的最终目标是求解最小化数组中的最大整数值。使用整数除法可以直接得到不超过平均值的最大整数，这符合问题中最大值的定义（即数组中的每个元素都是整数）。如果使用浮点数除法，虽然可以得到更精确的平均值，但最终结果仍需取整，因此直接使用整数除法可以简化计算过程且不会影响结果的正确性。
这种方法仍然适用于包含0或非常小的值的数组。因为前缀和与索引的商本质上是求解在当前索引前（包括当前索引）的所有元素平均分配的结果，0或非常小的值在计算平均分配时会被其他较大的值平衡。因此，这种值的存在不会影响最终计算出的最大值的最小可能值，只会在计算平均分配时作为平均数的一部分。
前缀和数组通过计算到每个索引为止的所有元素之和，配合索引商的计算，可以确保考虑了从数组开始到任何一个位置的所有分配可能性。对每个前缀进行商的计算，实际上是在考虑如果将该前缀区间内的所有元素平均分配，每个元素最多可以是多少。因此，这种方法通过遍历所有可能的前缀和来确保考虑了所有可能的分配方案，从而找到在这些分配方案中能够实现的最大值的最小可能值，这就保证了在所有可能的情况下得到了最优解。