逐步取得正值Leetcode解决方案的最小值


难度级别 易得奖学金
经常问 Swiggy
排列

问题陈述

在这个问题中,我们得到了一个数字序列(可以是正负或零)。 我们必须随身携带一个正整数,然后我们将开始添加该整数 排列 从左到右。
我们想要开始时应该采用的最小正整数,以便在任何时候我们的当前总和始终保持正数。

使用案列

nums = [-3,2,-3,4,2]
5

说明:

逐步取得正值Leetcode解决方案的最小值
我们在这里可以看到,如果选择startValue = 5,则所有中间和为正。 我们也可以检查startValue = 4,这不是正确的解决方案。

nums = [1,2]
1

说明:

最小起始值应为正。

途径

假设我们有array,nums = [-3,2,-3,4,2]
现在,如果我们选择初始值为2,并继续从左到右添加元素,则:

逐步取得正值Leetcode解决方案的最小值

在上面的示例中,我们选择初始值为2。我们的总和不会每次都保持正值,因此我们需要一些更大的元素。

令初始val为5。
逐步取得正值Leetcode解决方案的最小值
现在,我们可以清楚地看到,如果起始值为5,那么我们肯定可以遍历整个数组,并始终保持当前和为正。 如果它是最小的整数,则5可以作为答案。
让我们考虑一下如果我们一开始就选择val = 0的情况。

逐步取得正值Leetcode解决方案的最小值

现在,我们可以说,如果我们克服了大多数负电流之和(在当前示例中为-4)的值,那么我们可以毫无问题地通过数组。
就像在上面的示例中,最大负值是-4。要克服它,我们必须将其设置为1(因为需要最小的正整数)。

因此,我们希望值1-(-4)= 5通过最负面的情况。
我们还看到5可以通过解决方案。

如果没有负电流总和,我们将只输出1,因为我们想要一个正整数解。

因此,我们的算法将是:

1.我们必须寻找最否定的解决方案,因此我们将遍历整个数组。
2.在每次迭代中 循环 我们将检查当前总和是否为最小值,并相应地更新最小值。
3.最后,将这个最大负值设为1,我们只需将其从1中减去(例如,如果min = -4,val = 1-(-4)= 5)。

实施

最小值的C ++程序,逐步获得总Leetcode解决方案

#include <iostream>
#include<vector>
using namespace std;

int minStartValue(vector<int>& nums) {
    
    int min=0,sum=0;
    for (int i = 0; i < nums.size(); i++){
        sum+=nums[i];
        min=min<sum?min:sum;
    }
    
    return 1-min;
}

int main() {
    vector<int> nums{-3,2,-3,4,2}; 
    cout<<minStartValue(nums)<<endl;	
  return 0;
}
5

最小值的Java程序,逐步获得总的Leetcode解决方案

import java.util.*;

class Rextester{
    
    public static int minStartValue(int[] nums) 
    {
        Integer min=0,sum=0;
        for(int i:nums){
            sum+=i;
            min=Math.min(min,sum);
        }
        return 1-min;
    }
    
    public static void main(String args[])
    {
       	int[]nums={-3,2,-3,4,2};
        int ans=minStartValue(nums);
        System.out.println(ans);
    }
}
5

最小值的复杂度分析,逐步求和Leetcode解决方案

时间复杂度

上): 因为我们正在线性遍历给定数组,所以我们的时间复杂度将为O(n)。

空间复杂度 

O(1): 我们没有使用任何额外的空间,因此我们的空间复杂度将保持不变。