逐步求和得到正数的最小值

难度: Easy

给你一个整数数组 nums 。你可以选定任意的正数 startValue 作为初始值。

你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。

请你在确保累加和始终大于等于 1 的前提下，选出一个最小的正数作为 startValue 。

示例 1：

输入：nums = [-3,2,-3,4,2]
输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。
                累加求和
                startValue = 4 | startValue = 5 | nums
                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

示例 2：

输入：nums = [1,2]
输出：1
解释：最小的 startValue 需要是正数。

示例 3：

输入：nums = [1,-2,-3]
输出：5

提示：

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Submission

运行时间: 16 ms

内存: 16.5 MB

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        min_num=101
        cur=0
        for i in range(len(nums)):
            cur+=nums[i]
            min_num=min(min_num,cur)
        return 1-min_num if 1-min_num>0 else 1

Explain

此题解的思路是先遍历数组，同时计算从开始到当前元素的累加和，记录过程中累加和的最小值。最终，为了确保任何时刻累加和都不小于1，计算必须的起始值为 1 减去这个累加和的最小值。如果这个值小于等于0，则返回1作为起始值（因为起始值要求是正数）。这种方法避免了多次尝试不同起始值的情况，直接通过一次遍历得到结果。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        min_num = 101  # 初始化最小累加和为101，因为累加和的最小可能值比所有可能的nums元素和还要小
        cur = 0  # 当前累加和初始化为0
        for i in range(len(nums)):
            cur += nums[i]  # 更新当前累加和
            min_num = min(min_num, cur)  # 更新遍历过程中的最小累加和
        # 计算最小起始值。如果1 - min_num <= 0，返回1，否则返回1 - min_num
        return 1 - min_num if 1 - min_num > 0 else 1

Explore

在初始化 min_num 为 101 的选择是基于一个假设，即无论数组中的元素如何，累加和的最小值不会超过这个数。这种方法确实可以工作，但不是最优的。更合适的初始化方法是将 min_num 初始化为 0，因为累加和的最小值从 0 开始计算。这样可以确保无论数组如何变化，min_num 都是从最初始的累加和开始比较，避免了选择任意大的初始值。

如果数组 nums 全由正数构成，累加和 cur 从第一个元素开始始终是增加的，因此 min_num 只在第一次迭代时被更新（假设 min_num 初始值设置为大于数组中任何元素的值）。这意味着，min_num 将是数组中的第一个元素值。由于每一步累加和都是正的，这将导致最终的 min_num 也是正数，从而计算出的起始值至少为 1。因此，最终结果仍然保证算法的正确性。

使用 min 函数来更新 min_num 是一种简单且直观的方式，保证了每一次累加后能立即得到最小值。尽管这种方法有效，但每次循环都需要进行一次比较。若要减少比较次数，可以考虑在循环开始前将 min_num 初始化为数组第一个元素的值（假设数组非空），然后从第二个元素开始迭代，这样可以省去与初始非实际累加和的比较。

确实如此。如果 min_num >= 1，说明在任何时候累加和都没有小于1，因此起始值1已经足够确保所有的前缀和都是正数。故在这种情况下，不需要进一步增加起始值，直接返回1即可满足题目要求。