首页 > 代码库 > Candy
Candy
地址:https://oj.leetcode.com/problems/candy/
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
其实最终就是需要满足高的rating比他邻居获得更多糖果。最简单办法就是先从头到尾设置一次糖果分配数,如果比前面一个rating 高则分糖果数加1,如果不高则先赋值1。然后从尾到头再次遍历一次,从而使得高rating必然获得比邻居更多的糖果。
public class Solution { public int candy(int[] ratings) { if(ratings.length == 0){ return 0; } // 算法思想:从头到尾遍历数组,如果满足rating 更大 就给A[i-1]+1个,如果小就先赋值1. int []A = new int[ratings.length]; A[0] = 1; for(int i=1;i<ratings.length;i++){ if(ratings[i]>ratings[i-1]){ A[i]= A[i-1]+1; }else { A[i] = 1; } } int ans = A[ratings.length-1]; // 从尾到头再遍历一次,两次遍历过后就满足更高rating 有用更多糖果。 for(int i=ratings.length-2;i>=0;i--){ if(ratings[i]>ratings[i+1]){ A[i] = Math.max(A[i], A[i+1]+1); } ans+= A[i]; } return ans; }}
Candy
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。