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

---

题目链接：1413. 逐步求和得到正数的最小值

题目描述

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

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

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

提示:

• 1⩽nums.length⩽1001 \leqslant nums.length \leqslant 1001⩽nums.length⩽100
• −100⩽nums[i]⩽100-100 \leqslant nums[i] \leqslant 100−100⩽nums[i]⩽100

示例 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

整理题意

题目要求我们 任意 选取一个 正整数 作为起始值 startValue，然后将数组从头到尾累加，需要保证过程中累加和始终大于等于 1，让我们求最小的起始值 startValue。

解题思路分析

我们首先对整个数组从头到尾进行累加求和，记录累加求和的过程中的最小值 m，根据 贪心 思想，只要我们保证这个最小值为正数即可保证累加求和的过程中都为正数。又因为起始值 startValue 为正整数，那么最小的 startValue 为 1。

具体实现

1. 初始化累加求和过程中最小值 m 为 0；
2. 从左到右遍历数组，记录累加和 sum，过程中不断维护最小值 m；
3. 为了使得累加求和的过程中都为正数，那么我们的起始值应该为 -m + 1，+1 是因为题目要求 startValue 为正整数。

复杂度分析

• 时间复杂度：O(n)O(n)O(n)，其中 n 是数组 nums 的长度。只需要遍历数组一次。
• 空间复杂度：O(1)O(1)O(1)。只需要使用常量空间。

代码实现

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

总结

• 该题的题目描述比较难懂，需要我们自己将题目描述进行解读，难点应该就在题目的解读上了，读懂题目后该题就为简单的 贪心 题，利用 前缀和 进行 贪心 求解即可。
• 需要注意的是该题的起始值 startValue 必须为整数，所以最小值为 1；
• 测试结果：

结束语

发现快乐，你的生活就多一些亮色；学会共赢，你的工作会少一些争执；懂得感恩，你的世界便多几分温柔；守住原则，你的人生将少几分迷茫。良好的思维习惯，会让你赢得更多的机会，遇见更好的自己。从现在开始改变思维方式，你将拥有更大的人生格局。新的一天，加油！