Leetcode 1413:逐步求和得到正数的最小值(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1413:逐步求和得到正数的最小值(超详细的解法!!!)

in leetcode with 0 comment

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

提示:

解题思路

首先不难想到通过二分法来处理这个问题,每次判断当前数mid是不是满足条件,如果满足条件,那么在[l,mid]中继续查找;否则,在[mid + 1, r]中继续查找。

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        l, r = 1, 10010
        
        def check(k):
            cur, pre = 0, k
            for i in nums:
                cur = pre + i
                if cur < 1: return False
                pre = cur
            return True
        
        while l < r:
            mid = (l + r) >> 1
            if check(mid):
                r = mid
            else:
                l = mid + 1
        return l

还有一个更加简洁的思路,实际上我们可以记录nums从前向后累加过程中的最小值min_sum,那么最后的结果就是-min_sum + 1

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        pref, min_pref = 0, 0
        for i in nums:
            pref += i
            min_pref = min(min_pref, pref)
        return 1 - min_pref

reference:

https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/discuss/585560/C%2B%2BJava-O(n)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses