题解 | #分糖果#

原题： 有N个小朋友站在一排，每个小朋友都有一个评分 你现在要按以下的规则给孩子们分糖果： 每个小朋友至少要分得一颗糖果 分数高的小朋友要他比旁边得分低的小朋友分得的糖果多 你最少要分发多少颗糖果？

示例：

[1,2,2]
4

[2,4,2]
4

[5,3,1]
6

注释详解：

import java.util.*;


public class Solution {
    /**
     * 
     * @param ratings int整型一维数组 
     * @return int整型
     */
    public static int candy(int[] ratings) {
        // write code here
        // 记录每人手中糖果数量
        int[] counts = new int[ratings.length];
        counts[0] = 1;
        // 从左到右遍历
        for (int j = 1; j < ratings.length; j++) {
            // 如果当前数大于左侧前一位
            if (ratings[j] > ratings[j - 1]) {
                // 当前数分到的糖果比前一位多一个
                counts[j] = counts[j - 1] + 1;
            } else {
                // 保底一个
                counts[j] = 1;
            }
        }

        // 从右到左遍历
        for (int i = ratings.length - 2; i >= 0; i--) {
            // 如果当前数大于右侧前一位
            if (ratings[i] > ratings[i + 1]) {
                // 取当前数右侧一位的糖果数+1与当前数之前记录的糖果数比较,最大的一个当作当前数的糖果数
                counts[i] = Math.max(counts[i], counts[i + 1] + 1);
            }
        }
        
        int result = 0;
        for (int n : counts) {
            result += n;
        }

        return result;
    }