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

相关推荐

  • leetcode9-回文数

    原题 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例1: 输入: 121 输出: true 示例2: 输入: -121 输出: fa…

    算法 2020年2月28日
    0110
  • leetcode887-鸡蛋掉落

    原题 你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 F ,满足 0 &…

    算法 2020年4月11日
    0120
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode105-从前序与中序遍历序列构造二叉树

    原题 根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inord…

    算法 2020年1月13日
    090
  • 海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源: 那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天…

    2020年2月28日
    01.3K0
  • leetcode1095-山脉数组中查找目标值

    原题 (这是一个 交互式问题 ) 给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 in…

    算法 2020年4月29日
    0140
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • leetcode236-二叉树的最近公共祖先

    原题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 …

    2020年1月15日
    060
  • leetcode410-分割数组的最大值

    原题 给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意:数组长度 n 满足以下条件: 1…

    算法 2020年1月9日
    0580
  • leetcode54-螺旋矩阵

    原题 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6…

    算法 2019年11月15日
    080

发表回复

登录后才能评论