[1413. Stepwise summation to get the minimum value of positive numbers]

来源：力扣（LeetCode）

描述：

给你一个整数数组 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

方法一：贪心

思路

All cumulative sums are guaranteed accSum 满足 accSum + startValue ≥ 1,Just keep the minimum value of the accumulated sum accSumMin 满足 accSumMin + startValue ≥ 1,那么 startValue The minimum value of −accSumMin + 1.

代码：

class Solution {
    
public:
    int minStartValue(vector<int>& nums) {
    
        int accSum = 0, accSumMin = 0;
        for (int num : nums) {
    
            accSum += num;
            accSumMin = min(accSumMin, accSum);
        }
        return -accSumMin + 1;
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.2 MB, 在所有 C++ 提交中击败了17.09%的用户
复杂度分析
时间复杂度： O(n),其中 n 是数组 nums 的长度.Only need to iterate over the array once.
空间复杂度： O(1).Just use constant space.

方法二：二分查找

思路

当 nums When all elements are non-negative,可以直接返回 1.当有负数时,可以

when a certain number is satisfied startValue 的要求时,Larger numbers are certainly satisfied,A number smaller than it is not necessarily sufficient,因此 startValue is monotonic in nature,This problem can be solved by binary search.The left starting point for binary search is 1,The right starting point can be set to nums The inverse of the minimum value of is multiplied by the length and added 1,This ensures that the right endpoint must be satisfied startValue 的要求.

Determine whether a certain number is satisfied startValue 的要求时,可以将 nums The number is gradually added to this number,It can be judged whether it is always positive.

代码：

class Solution {
    
public:
    int minStartValue(vector<int>& nums) {
    
        int m = *min_element(nums.begin(), nums.end());
        if (m >= 0) {
    
            return 1;
        }
        int left = 1, right = -m * nums.size() + 1;
        while (left < right) {
    
            int medium = (left + right) / 2;
            if (valid(medium, nums)) {
    
                right = medium;
            } else {
    
                left = medium + 1;
            }
        }
        return left;
    }

    bool valid(int startValue, vector<int>& nums) {
    
        for (int num : nums) {
    
            startValue += num;
            if (startValue <= 0) {
    
                return false;
            }
        }
        return true;
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.1 MB, 在所有 C++ 提交中击败了78.80%的用户
复杂度分析
时间复杂度： O(n × log(mn)),其中 n 是数组 nums 的长度, m is the absolute value of the minimum value of the array.The number of binary searches is O(log(mn)),每次消耗 O(n).
空间复杂度： O(1).Just use constant space.
author：LeetCode-Solution