本文共 1055 字,大约阅读时间需要 3 分钟。
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:
What is the minimum candies you must give?
Java代码:public class Solution { public int candy(int[] ratings) { int len = ratings.length; if (0 == len) return 0; if (1 == len) return 1; int num = 0; int[] candys = new int[len]; for (int i = 0; i < len; i++) candys[i] = 1; for (int i = 0; i < len - 1; i++) { if (ratings[i] < ratings[i + 1]) candys[i + 1] = candys[i] + 1; } for (int i = len - 1; i > 0; i--) { if (ratings[i] < ratings[i - 1]) if (i != 1){ if (ratings[i - 2] >= ratings[i - 1]) candys[i - 1] = candys[i] + 1; else candys[i - 1] = Math.max(candys[i - 2], candys[i]) + 1; }else{ candys[i - 1] = candys[i] + 1; } } int sum = 0; for (int i = 0; i < len; i++) { sum += candys[i]; } return sum; }}
转载地址:http://hsuni.baihongyu.com/