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

链接：1413.逐步求和得到正数的最小值
难度：Easy
标签：数组、前缀和
简介：请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue 。

题解 1 - rust

• 编辑时间：2022-08-09
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：二分。

fn check(nums: &Vec<i32>, v: i32) -> bool {
    let mut v = v;
    for num in nums {
        v += num;
        if v <= 0 {
            return false;
        }
    }
    true
}
impl Solution {
    pub fn min_start_value(nums: Vec<i32>) -> i32 {
        let (mut l, mut r) = (1, i32::MAX);
        while l < r {
            let m = l + (r - l) / 2;
            if check(&nums, m) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l
    }
}

题解 2 - rust

• 编辑时间：2022-08-09
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：前缀和判断每一次数组中值相加的绝对值小于 ans。

impl Solution {
    pub fn min_start_value(nums: Vec<i32>) -> i32 {
        let (mut ans, mut sum) = (0, 0);
        for num in nums {
            sum += num;
            ans = ans.min(sum);
        }
        ans.abs() + 1
    }
}

题解 3 - rust

• 编辑时间：2022-08-09
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：前缀和判断每一次数组中值相加的绝对值小于 ans。

impl Solution {
    pub fn min_start_value(nums: Vec<i32>) -> i32 {
        let mut ans = 1;
        let mut sum  = 0;
        for num in nums {
            sum += num;
            if sum < 0 && ans <= sum.abs() {
                ans = sum.abs() + 1;
            }
        }
        ans
    }
}