【1413. 逐步求和得到正数的最小值】

来源：力扣（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
1
2
3
4
5
6
7
8
9
10

示例 2：

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

示例 3：

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

提示：

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

方法一：贪心

思路

要保证所有的累加和 accSum 满足 accSum + startValue ≥ 1，只需保证累加和的最小值 accSumMin 满足 accSumMin + startValue ≥ 1，那么 startValue 的最小值即可取 −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;
    }
};
1
2
3
4
5
6
7
8
9
10
11

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.2 MB, 在所有 C++ 提交中击败了17.09%的用户
复杂度分析
时间复杂度： O(n)，其中 n 是数组 nums 的长度。只需要遍历数组一次。
空间复杂度： O(1)。只需要使用常量空间。

方法二：二分查找

思路

当 nums 所有元素均为非负数时，可以直接返回 1。当有负数时，可以

当某个数字满足 startValue 的要求时，比它大的数字肯定也都满足，比它小的数字则不一定能满足，因此 startValue 的性质具有单调性，此题可以用二分查找来解决。二分查找的左起始点为 1，右起始点可以设为 nums 的最小值的相反数乘上长度后再加 1，这样可以保证右端点一定满足 startValue 的要求。

判断某个数字是否满足 startValue 的要求时，可以将 nums 的数字逐步加到这个数字上，判断是否一直为正即可。

代码：

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;
    }
};
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
27
28
29

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.1 MB, 在所有 C++ 提交中击败了78.80%的用户
复杂度分析
时间复杂度： O(n × log(mn))，其中 n 是数组 nums 的长度， m 是数组最小值的绝对值。二分查找的次数是 O(log(mn))，每次消耗 O(n)。
空间复杂度： O(1)。只需要使用常量空间。
author：LeetCode-Solution