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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

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

方法一：贪心

思路

要保证所有的累加和 accSum 满足 accSum} + \textit{startValue} \ge 1，只需保证累加和的最小值 accSumMin 满足 accSumMin} + \textit{startValue} \ge 1，那么 startValue 的最小值即可取 -\textit{accSumMin} + 1。

代码

[sol1-Python3]
1
2
3
4
5
6
7
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
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minStartValue(int[] nums) {
        int accSum = 0, accSumMin = 0;
        for (int num : nums) {
            accSum += num;
            accSumMin = Math.min(accSumMin, accSum);
        }
        return -accSumMin + 1;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int MinStartValue(int[] nums) {
        int accSum = 0, accSumMin = 0;
        foreach (int num in nums) {
            accSum += num;
            accSumMin = Math.Min(accSumMin, accSum);
        }
        return -accSumMin + 1;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int accSum = 0, accSumMin = 0;
        for (int num : nums) {
            accSum += num;
            accSumMin = min(accSumMin, accSum);
        }
        return -accSumMin + 1;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int minStartValue(int* nums, int numsSize){
    int accSum = 0, accSumMin = 0;
    for (int i = 0; i < numsSize; i++) {
        accSum += nums[i];
        accSumMin = MIN(accSumMin, accSum);
    }
    return -accSumMin + 1;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func minStartValue(nums []int) int {
    accSum, accSumMin := 0, 0
    for _, num := range nums {
        accSum += num
        accSumMin = min(accSumMin, accSum)
    }
    return -accSumMin + 1
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
var minStartValue = function(nums) {
    let accSum = 0, accSumMin = 0;
    for (const num of nums) {
        accSum += num;
        accSumMin = Math.min(accSumMin, accSum);
    }
    return -accSumMin + 1;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。只需要遍历数组一次。

  • 空间复杂度：O(1)。只需要使用常量空间。

方法二：二分查找

思路

当 nums 所有元素均为非负数时，可以直接返回 1。当有负数时，可以

当某个数字满足 startValue 的要求时，比它大的数字肯定也都满足，比它小的数字则不一定能满足，因此 startValue 的性质具有单调性，此题可以用二分查找来解决。二分查找的左起始点为 1，右起始点可以设为 nums 的最小值的相反数乘上长度后再加 1，这样可以保证右端点一定满足 startValue 的要求。

判断某个数字是否满足 startValue 的要求时，可以将 nums 的数字逐步加到这个数字上，判断是否一直为正即可。
代码

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minStartValue(int[] nums) {
        int m = Arrays.stream(nums).min().getAsInt();
        if (m >= 0) {
            return 1;
        }
        int left = 1, right = -m * nums.length + 1;
        while (left < right) {
            int medium = (left + right) / 2;
            if (valid(medium, nums)) {
                right = medium;
            } else {
                left = medium + 1;
            }
        }
        return left;
    }

    public boolean valid(int startValue, int[] nums) {
        for (int num : nums) {
            startValue += num;
            if (startValue <= 0) {
                return false;
            }
        }
        return true;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int MinStartValue(int[] nums) {
        int m = nums.Min();
        if (m >= 0) {
            return 1;
        }
        int left = 1, right = -m * nums.Length + 1;
        while (left < right) {
            int medium = (left + right) / 2;
            if (Valid(medium, nums)) {
                right = medium;
            } else {
                left = medium + 1;
            }
        }
        return left;
    }

    public bool Valid(int startValue, int[] nums) {
        foreach (int num in nums) {
            startValue += num;
            if (startValue <= 0) {
                return false;
            }
        }
        return true;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int m = *min_element(nums.begin(), nums.end());
        if (m >= 0) {
            return 1;
        }
        int left = 1, right = -m * nums.size() + 1;
        while (left < right) {
            int medium = (left + right) / 2;
            if (valid(medium, nums)) {
                right = medium;
            } else {
                left = medium + 1;
            }
        }
        return left;
    }

    bool valid(int startValue, vector<int>& nums) {
        for (int num : nums) {
            startValue += num;
            if (startValue <= 0) {
                return false;
            }
        }
        return true;
    }
};
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define MIN(a, b) ((a) < (b) ? (a) : (b))

bool valid(int startValue, const int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        startValue += nums[i];
        if (startValue <= 0) {
            return false;
        }
    }
    return true;
}

int minStartValue(int* nums, int numsSize){
    int m = nums[0];
    for (int i = 1; i < numsSize; i++) {
        m = MIN(m, nums[i]);
    }
    if (m >= 0) {
        return 1;
    }
    int left = 1, right = -m * numsSize + 1;
    while (left < right) {
        int medium = (left + right) / 2;
        if (valid(medium, nums, numsSize)) {
            right = medium;
        } else {
            left = medium + 1;
        }
    }
    return left;
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func minStartValue(nums []int) int {
    m := nums[0]
    for _, num := range nums[1:] {
        m = min(m, num)
    }
    return 1 + sort.Search(-m*len(nums), func(startValue int) bool {
        startValue++
        for _, num := range nums {
            startValue += num
            if startValue <= 0 {
                return false
            }
        }
        return true
    })
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var minStartValue = function(nums) {
    const m = _.min(nums);
    if (m >= 0) {
        return 1;
    }
    let left = 1, right = -m * nums.length + 1;
    while (left < right) {
        const medium = Math.floor((left + right) / 2);
        if (valid(medium, nums)) {
            right = medium;
        } else {
            left = medium + 1;
        }
    }
    return left;
};

const valid = (startValue, nums) => {
    for (const num of nums) {
        startValue += num;
        if (startValue <= 0) {
            return false;
        }
    }
    return true;
}

复杂度分析

  • 时间复杂度：O(n \times \log (mn))，其中 n 是数组 nums 的长度，m 是数组最小值的绝对值。二分查找的次数是 O(\log (mn))，每次消耗 O(n)。

  • 空间复杂度：O(1)。只需要使用常量空间。

 Comments
On this page
1413-逐步求和得到正数的最小值