博客

前言


提示：以下是本篇文章正文内容，编程语言为Java


一、题目描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

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

相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

链接：

分发糖果

二、解题思路

我们可以将

相邻的孩子中，评分高的孩子必须获得更多的糖果

这句话拆分为两个规则，分别处理：


1）左规则。

我们从左向右分发糖果，右边评分比左边高的就多给右边孩子一个糖果，否则就给他一个。


2）右规则。

我们从右向左分发糖果，左边评分比右边高的就多给左边孩子一个糖果，否则就给他一个。

因为我们的糖果很少，我们只能给每个孩子分发糖果一次。当然，我们是比较大方的，所以我们拿两个规则中较多的糖果给孩子，这样孩子会很开心，我们也按规则完成了任务。

三、示例代码

class Solution {
    public int candy(int[] ratings) {
        int n=ratings.length;
        int[]ans1=new int[n];
        int[]ans2=new int[n];
        
        //左规则
        ans1[0]=1;
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1]){
                ans1[i]=ans1[i-1]+1;
            }
            else{
                ans1[i]=1;
            }
        }
        
        //右规则
        ans2[n-1]=1;
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                ans2[i]=ans2[i+1]+1;
            }
            else{
                ans2[i]=1;
            }
        }
        //两个规则中孩子实际得到的是糖果较多的
        int ans=0;
        for(int i=0;i<n;i++){
            ans+=Math.max(ans1[i],ans2[i]);  
        }
        return ans;
        
    }
}

总结

当题目的规则比较苛刻时，我们可以考虑将它分成多个规则来处理，也许就能简化问题，从而更轻松的完成题目。