leetcode135-分发糖果

原题

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中,评分高的孩子必须获得更多的糖果。

那么这样下来,老师至少需要准备多少颗糖果呢?

示例1:

输入: [1,0,2] 输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例2:

输入: [1,2,2] 输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

解法

思想

要满足相邻的孩子中,评分高的孩子必须获得更多的糖果,可以进行左右各一次动态规划,每次只保证满足一边评分高的孩子获得更多糖果。

代码

class Solution {
    public int candy(int[] ratings) {
        int length = ratings.length;
        int[] left = new int[length];
        int[] right = new int[length];
        for(int i = 1; i < length; i++)
            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        int count = left[length - 1];
        for(int i = length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            count += Math.max(left[i], right[i]);
        }
        return count+length;
    }
}
func candy(ratings []int) int {
    left := make([]int, len(ratings))
    right := make([]int, len(ratings))
    for i := 0; i < len(ratings); i ++ {
        if i == 0 {
            right[i] = 1
        } else{
            if ratings[i] > ratings[i-1] {
                right[i] = right[i-1] + 1
            } else{
                right[i] = 1
            }
        }
    }
    for i := len(ratings)-1; i >= 0; i -- {
        if i == len(ratings)-1 {
            left[i] = 1
        } else{
            if ratings[i] > ratings[i+1] {
                left[i] = left[i+1] + 1
            } else{
                left[i] = 1
            }
        }
    }
    count := 0
    for i := 0; i < len(ratings); i ++ {
       count += max(left[i], right[i]) 
    }
    return count
}

相关题

leetcode238-除自身以外数组的乘积

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode135-%e5%88%86%e5%8f%91%e7%b3%96%e6%9e%9c/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月17日 02:14
下一篇 2020年2月17日 13:56

相关推荐

  • leetcode456-132模式

    原题 给定一个整数序列:a1, a2, ..., an,一个132模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak &lt…

    算法 2020年1月30日
    0150
  • leetcode402-移掉K位数字

    原题 给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 …

    算法 2020年1月29日
    090
  • leetcode701-二叉搜索树中的插入操作

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

    算法 2020年1月16日
    0100
  • leetcode300-最长上升子序列

    原题 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10…

    算法 2020年3月14日
    0250
  • 剑指offer62-圆圈中最后剩下的数字

    原题(来源Leetcode) 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如,0、1、2、3、4这5…

    算法 2020年3月30日
    0650
  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050
  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以…

    算法 2019年11月14日
    0140
  • 剑指offer51-数组中的逆序对

    原题(来源Leetcode) 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7…

    算法 2020年4月24日
    0400
  • leetcode11-盛最多水的容器

    原题 给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i,…

    2020年2月27日
    0250
  • leetcode771-宝石与石头

    原题 给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复,J …

    算法 2019年12月26日
    0360

发表回复

登录后才能评论