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

原题

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

解法

思想

找到最小的前缀和,算出与1的差值。(如果大于等于1则返回1)

代码

class Solution {
    public int minStartValue(int[] nums) {
        int min = nums[0];
        for(int i = 1;i < nums.length;i++){
            nums[i] += nums[i-1];
            if(nums[i]<min) min = nums[i]; 
        }
        return min>=1 ? 1 : 1-min;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1413-%e9%80%90%e6%ad%a5%e6%b1%82%e5%92%8c%e5%be%97%e5%88%b0%e6%ad%a3%e6%95%b0%e7%9a%84%e6%9c%80%e5%b0%8f%e5%80%bc/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月19日
下一篇 2020年6月26日

相关推荐

  • leetcode128-最长连续序列

    原题 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长…

    算法 2020年6月6日
    080
  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0120
  • leetcode32-最长有效括号

    原题 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2…

    算法 2020年6月12日
    0140
  • leetcode287-寻找重复数

    原题 给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 …

    2020年1月7日
    080
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0100
  • leetcode724-寻找数组的中心索引

    原题 给定一个整数类型的数组nums,请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数…

    算法 2019年11月13日
    0130
  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0160
  • leetcode74-搜索二维矩阵

    原题 编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性: 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。   示例…

    算法 2020年4月29日
    0160
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110

发表回复

登录后才能评论