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

正数的最小值"/>

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

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

我的解法：

class Solution {vector<int> sum;
public:int minStartValue(vector<int>& nums) {sum.resize(nums.size()+1);int ans = 1;while(true){sum[0] = ans;for(int i=1;i<=nums.size();i++){sum[i] = sum[i-1] + nums[i-1];if(sum[i] < 1) break;if(i == nums.size()) return ans;}ans++;}}
};

因为是前缀和的题，所以我都是在想用前缀和的思路解题，前缀和数组的0号元素为startValue，加上nums数组元素后小于1则为错解，如果加到最后仍大于1则返回结果。

最坏时间复杂度:nums数组元素均为-100，则startValue为10001，则循环次数为（1+2+3+···+100）x100 = 505000

最好时间复杂度：ans=1，也要循环一次nums数组。

空间复杂度：O(n)，n为nums的长度

官方解法：

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;}
};

要保证所有的累加和 accSum 满足 accSum+startValue≥1，只需保证累加和的最小值 accSumMin满足 accSumMin+startValue≥1，那么 startValue的最小值即可取 −accSumMin+1

时间复杂度：O(n)

空间复杂度：O(1),只需要使用常量空间。

2.二分法

class Solution {
public:int minStartValue(vector<int>& nums) {//m为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;}
};

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

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

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

时间复杂度：O(n×log⁡(mn))，其中 n 是数组 nums 的长度，mmm 是数组最小值的绝对值。二分查找的次数是 O(log(mn))，每次消耗 O(n)。

空间复杂度：O(1),只需要使用常量空间。

其实二分法是我的思路的优化，但是我没有想到，以后注意。