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

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

题目：给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。
你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。
请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue

链接 https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum

个人思路

1. 逐个相加，找出相加过程中的最小值，当最小值小于0时，返回其相反数加1，当最小值大于等于0时，返回1即可。
   （贪心算法）

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        temp = 0
        total = 0
        for i in nums:
            total += i
            if total < temp:
                temp = total
        if temp <= 0:
            return 1 - temp
        else:
            return 1
1
2
3
4
5
6
7
8
9
10
11
12

其实也不需要判断是否小于0：

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        accSum, accSumMin = 0, 0
        for num in nums:
            accSum += num
            accSumMin = min(accSumMin, accSum)
        return -accSumMin + 1
1
2
3
4
5
6
7

复杂度分析
时间复杂度：O(n)，其中 n 是数组nums 的长度。只需要遍历数组一次。
空间复杂度：O(1)。只需要使用常量空间。

其他思路

1. 二分查找
   （1）当 nums 所有元素均为非负数时，可以直接返回 1。
   （2）当有负数时，可以当某个数字满足startValue 的要求时，比它大的数字肯定也都满足，比它小的数字则不一定能满足，因此startValue 的性质具有单调性，此题可以用二分查找来解决。二分查找的左起始点为 1，右起始点可以设为 nums 的最小值的相反数乘上长度后再加 1，这样可以保证右端点一定满足 startValue 的要求。
   （3）判断某个数字是否满足 startValue 的要求时，可以将 nums 的数字逐步加到这个数字上，判断是否一直为正即可。

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        m = min(nums)
        if m >= 0:
            return 1
        left, right = 1, -m * len(nums) + 1
        while left < right:
            medium = (left + right) // 2
            if self.valid(medium, nums):
                right = medium
            else:
                left = medium + 1
        return left
    
    def valid(self, startValue: int, nums: List[int]) -> bool:
        for num in nums:
            startValue += num
            if startValue <= 0:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这方法用在这里显得有点多余。。。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum/solution/zhu-bu-qiu-he-de-dao-zheng-shu-de-zui-xi-vyrt/