【LeetCode】逐步求和得到正数的最小值 Java 题解

作者：Albert

2022 年 8 月 09 日
北京
本文字数：1088 字
阅读完需：约 4 分钟

题目描述

给你一个整数数组 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
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的的算法题目数组题目,题目要求数组从左到右累加求和，确保累加和始终大于等于 1。经过分析，我们可以先遍历整体数组，找出最小的值，如果都是正数，那答案就是 1。如果有负数，那我们取绝对值之后在加上 1。确定左右区间，我们可以使用二分查找算法，来判断是否满足需求。这里需要注意的是，取右端点的时候，需要计算上数组的长度，确保又端点满足条件。具体实现代码如下，供参考。

通过代码

class Solution {    public int minStartValue(int[] nums) {        int minVal = Arrays.stream(nums).min().getAsInt();        if (minVal >= 0) {            return 1;        }        int left = 1, right = Math.abs(minVal) * nums.length + 1;        while (left < right) {            int medium = (left + right) / 2;            if (check(medium, nums)) {                right = medium;            } else {                left = medium + 1;            }        }        return left;    }
    private boolean check(int startValue, int[] nums) {        for (int num : nums) {            startValue += num;            if (startValue <= 0) {                return false;            }        }        return true;    }}