当前位置：首页 > article >正文

【LeetCode每日一题】——1413.逐步求和得到正数的最小值

article 2025/1/11 18:03:51

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目示例】
六【题目提示】
七【解题思路】
八【时间频度】
九【代码实现】
十【提交结果】

一【题目类别】

前缀和

二【题目难度】

简单

三【题目编号】

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

四【题目描述】

给你一个整数数组 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
所以我们直接对数组求和，在求和的过程中记录整个数组中每一位的最小累加和，因为只有获取到最小值，最后才能根据其计算出“抵消值”以确保数组每一位的累加和都要大于等于1（其实是贪心算法的思想），所以对于最后计算出的最小累加和有两种情况：
- 小于1：说明需要“抵消值”来确保数组每一位的累加和都要大于等于1，故返回“-最小累加和+1”
- 大于等于1：说明不需要“抵消值”来确保数组每一位的累加和都要大于等于1，因为原本数组每一位的累加和都已经大于等于1了，故根据题意直接返回1
最后返回结果即可
具体细节可以参考下面的代码

八【时间频度】

时间复杂度： $O (n)$ ， $n$ 为传入的数组的长度
空间复杂度： $O (1)$

九【代码实现】

Java语言版

class Solution {
    public int minStartValue(int[] nums) {
        // 记录总和
        int sum = 0;
        // 记录最小总和
        int min_sum = 0;
        // 找出最小总和
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            min_sum = Math.min(sum, min_sum);
        }
        // 如果最小总和小于1，需要抵消负数使其总和大于等于1，否则直接返回1
        return min_sum < 1 ? -min_sum + 1 : 1;
    }
}

Python语言版

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        # 记录总和
        total_sum = 0
        # 记录最小总和
        min_sum = 0
        # 找出最小总和
        for i in range(0, len(nums)):
            total_sum += nums[i]
            min_sum = min(total_sum, min_sum)
        # 如果最小总和小于1，需要抵消负数使其总和大于等于1，否则直接返回1
        if min_sum < 1:
            return -min_sum + 1
        else:
            return 1

C语言版

int minStartValue(int* nums, int numsSize)
{
    // 记录总和
    int sum = 0;
    // 记录最小总和
    int minSum = 0;
    // 找出最小总和
    for (int i = 0; i < numsSize; i++)
    {
        sum += nums[i];
        if (sum < minSum)
        {
            minSum = sum;
        }
    }
    // 如果最小总和小于1，需要抵消负数使其总和大于等于1，否则直接返回1
    return minSum < 1 ? -minSum + 1 : 1;
}