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

🟢   🔖  数组 前缀和  🔗 力扣 LeetCode

题目

Given an array of integers nums, you start with an initial positive value startValue.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

Example 1:

Input: nums = [-3,2,-3,4,2]

Output: 5

Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.

step by step sum

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

Example 2:

Input: nums = [1,2]

Output: 1

Explanation: Minimum start value should be positive.

Example 3:

Input: nums = [1,-2,-3]

Output: 5

Constraints:

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

题目大意

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

解题思路

1. 初始化变量：

   • 使用 sum 表示累加和，初始值为 0。
   • 使用 res 表示结果（即最小起始值），初始值为 1。

2. 遍历数组：

   • 对于数组中的每个元素 num，将其累加到 sum 中。
   • 每次更新结果 res，使其等于当前值与 1 - sum 的最大值。这是因为：
     • 如果 sum 的值小于 1，则需要更大的起始值以确保累加和不小于 1。
     • 更新规则：res = Math.max(res, 1 - sum)。

3. 遍历结束后，res 即为满足条件的最小起始值。

复杂度分析

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

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minStartValue = function (nums) {
	let sum = 0; // 累加和
	let res = 1; // 初始化结果
	for (let num of nums) {
		sum += num; // 更新累加和
		res = Math.max(res, 1 - sum); // 更新结果
	}
	return res; // 返回最小起始值
};