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?
- Example 1:
- Input: [1,0,2]
- Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
- Example 2:
- Input: [1,2,2]
- Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
实现题 (贪婪法)
1. 给所有孩子一颗糖.
2. 从左到右遍历, 把当前分数和左边比, 如果高了, 比左边的糖多一颗.
3. 从右到左遍历, 把当前分数和右边比, 如果高了, 比右边的糖多一颗.
4. 再扫一遍计数.
细节:
1. 第三步的时候, 如果要和右边比, 一定要从右到左扫, 不能从左到右扫. 如果从左到右, 因为你右边的对象还没有跟右边的右边的对象对比过, 它的值都还不是确定的, 你怎么能直接拿过来计算结果呢, 错误. 比如分数 321, 在和右边数对比的时候, 从左到右扫就会是 111->111->221 错误, 从右到左扫会是 111->111->321 正确
2. 给所有孩子一颗糖有优雅点的写法: Arrays.fill(array, 1);
实现:
- class Solution {
- public int candy(int[] ratings) {
- if (ratings == null || ratings.length == 0) {
- return 0;
- }
- int[] candies = new int[ratings.length];
- // P2: 一个优雅的填充写法.
- Arrays.fill(candies, 1);
- // for (int i = 0; i <candies.length; i++) {
- // candies[i] = 1;
- // }
- for (int i = 1; i < candies.length; i++) {
- if (ratings[i]> ratings[i - 1] && candies[i] <= candies[i - 1]) {
- candies[i] = candies[i- 1] + 1;
- }
- }
- // P1: 和右边的数字对比的时候, 要从右到左遍历, 否则会出错, 比如 321 的孩子, 在和右边数对比的时候, 从左到右扫就会是 111->111->221, 从右到左扫会是 111->111->321 正确
- for (int i = candies.length - 2; i>= 0; i--) {
- if (ratings[i]> ratings[i + 1] && candies[i] <= candies[i + 1]) {
- candies[i] = candies[i + 1] + 1;
- }
- }
- int ans = 0;
- for (int i = 0; i < candies.length; i++) {
- ans += candies[i];
- }
- return ans;
- }
- }
来源: http://www.bubuko.com/infodetail-2769585.html