LeetCode（#135）：分发糖果

一、前言

本题为LeetCode第135题，是一道 贪心算法 相关的算法题，难度困难。

本题链接：#135. 分发糖果

二、题目

有 N 个孩子站成了一条直线，每个孩子都有自己的评分。我们为这些孩子分发糖果，必须满足如下要求：

1. 每个孩子至少分配到 1 个糖果。

2. 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

求解最少需要多少颗糖果。

示例1：

Input:  [1, 0, 2]		// 孩子的评分
Output:   5				// 最少糖果的数量
// 分别给这三个孩子分发 2、1、2 颗糖果。

示例二：

Input:  [1,2,2]
Output:   4
// 分别给这三个孩子分发 1、2、1 颗糖果(第三个孩子只得到 1 颗糖果，同样满足要求)

三、思路

       首先分析题干要求，每个孩子至少一颗糖，评分比他两边的要高的孩子，获得的糖果也要比两边的多，求解给出糖果的最少数量。

       这也是一道求最优解的题目，并且考虑整体最优解（同时考虑两边的情况）比较复杂，可以根据贪心策略，将其拆分成一个个子问题，求局部最优解，最终合成整体最优解。

       同时考虑两边的情况很复杂，因此可以将左右两边分开进行考虑。由于每个孩子至少一颗糖，首先每个孩子都分到一颗糖。考虑右边的情况，即从左往右遍历孩子评分的数组，每遍历到一个孩子，只考虑他右侧的孩子是否比他评分高，若高于，则右侧孩子的糖果数更新为当前遍历到的孩子的糖果数+1，若低于/等于，则右侧孩子的糖果数保持不变。再考虑左边的情况，即从右往左遍历孩子评分的数组，比较左侧孩子与他的评分，若高于，且左侧孩子的糖果数不大于当前遍历到的孩子的糖果数，则左侧孩子的糖果数更新为当前遍历到的孩子的糖果数+1，若低于/等于，则左侧孩子的糖果数保持不变。

       通过这两次遍历，最终的糖果数即为最少糖果数。这里的贪心策略为：在每次遍历中，只考虑并更新左/右侧的大小关系（大于则+1，小于等于则不变）。

四、Java代码

public class solution {
    public int assignCandy(int[] ratings) {
        // 首先给每个孩子一颗糖
        int n = ratings.length;
        int[] candy = new int[n];
        Arrays.fill(candy, 1);
        
        // 从左往右遍历
        for(int i = 0; i < n-1; i++) {
            if( ratings[i+1] > ratings[i] ) {
                candy[i+1] = candy[i] + 1;
            }
        }
        
        // 从右往左遍历
        for(int i = n-1; i > 0; i--) {
            if( ratings[i-1] > ratings[i] && candy[i-1] <= candy[i] ) {
                candy[i-1] = candy[i] +1;
            }
        }
        
        // 计算并返回结果
        int count = 0;
        for(int i = 0; i < n; i++) count +=candy[i];
        return count;
    }
}

LeetCode（#135）：分发糖果

原文：https://www.cnblogs.com/ziqin/p/14589011.html