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

题目描述

这是 LeetCode 上的 1413. 逐步求和得到正数的最小值 ，难度为 简单。

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

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：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：
1
2
3
4
5
输入：nums = [1,2]

输出：1

解释：最小的 startValue 需要是正数。

示例 3：
1
2
3
输入：nums = [1,-2,-3]

输出：5

提示：

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

模拟

由于 startValue 可设定的最小值为 $1$，我们可以先统计当 startValue = 1 时，累加过程中的最小值 min。

根据 min 是否符合规定（大于等于 $1$）来决定如何调整：

  • 若 min 满足大于等于 $1$，则 startValue 可取最小值 $1$；
  • 若 min 不满足大于等于 $1$，计算将 min 调整到 $1$ 所需要的值（即 1 - min），将其累加到起始值上，即得答案 2 - min。

Java 代码：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minStartValue(int[] nums) {
        int n = nums.length, min = 0x3f3f3f3f;
        for (int i = 0, j = 1; i < n; i++) {
            j += nums[i];
            min = Math.min(min, j);
        }
        return min < 1 ? 2 - min : 1;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int n = nums.size(), minv = 0x3f3f3f3f;
        for (int i = 0, j = 1; i < n; i++) {
            j += nums[i];
            minv = min(minv, j);
        }
        return minv < 1 ? 2 - minv : 1;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        n, minv = len(nums), 0x3f3f3f3f
        j = 0
        for i in range(n):
            j += nums[i]
            minv = min(minv, j)
        return 1 if minv > 0 else 1 - minv

TypeScript 代码：
1
2
3
4
5
6
7
8
function minStartValue(nums: number[]): number {
    let n = nums.length, min = 0x3f3f3f3f
    for (let i = 0, j = 1; i < n; i++) {
        j += nums[i]
        min = Math.min(min, j)
    }
    return min < 1 ? 2 - min : 1
};

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1413 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。