数据结构与算法之LeetCode-1413. 逐步求和得到正数的最小值（贪心与排序）

news/2024/7/4 23:09:36

1413. 逐步求和得到正数的最小值 - 力扣（LeetCode）

/**
 * @param {number[]} nums
 * @return {number}
 */
 var minStartValue = function(nums) {
    let prev = 0,positive = false;
    for(let i=0;i<nums.length;i++){
        prev += nums[i]
        nums[i] = prev;
        if(prev>1){
            positive = true;
        }else{
            positive = false;
        }
    }

    prev = Math.min(...nums)
    if(prev<1){
        return -prev+1
    }else if(prev>=1){
        if(positive){
            return 1
        }
        return prev
    }
};

执行结果：通过

执行用时：68 ms, 在所有 JavaScript 提交中击败了16.47%的用户

内存消耗：41.1 MB, 在所有 JavaScript 提交中击败了41.18%的用户

通过测试用例：55 / 55

/**
 * @param {number[]} nums
 * @return {number}
 */
 var minStartValue = function(nums) {
    let prev = 0,positive = false,min=Infinity;
    for(let i=0;i<nums.length;i++){
        prev += nums[i]
        nums[i] = prev;
        if(prev<min){
            min = prev;
        }
        if(prev>1){
            positive = true;
        }else{
            positive = false;
        }
    }

    prev = min; // Math.min(...nums)
    if(prev<1){
        return -prev+1
    }else if(prev>=1){
        if(positive){
            return 1
        }
        return prev
    }
};

执行结果：通过

执行用时：60 ms, 在所有 JavaScript 提交中击败了61.18%的用户

内存消耗：40.8 MB, 在所有 JavaScript 提交中击败了84.71%的用户

通过测试用例：55 / 55

var minStartValue = function(nums) {
    let accSum = 0, accSumMin = 0;
    for (const num of nums) {
        accSum += num;
        accSumMin = Math.min(accSumMin, accSum);
    }
    return -accSumMin + 1;
};