[Leetcode] Candy 分糖果

張憲坤發(fā)布于2019-08-14 12:40 / 3014人閱讀

摘要：貪心法復(fù)雜度時間空間思路典型的貪心法，如果一個孩子比另一個孩子的分高，我們只多給塊糖。我們可以先從左往右遍歷，確保每個孩子根他左邊的孩子相比，如果分高，則糖要多個，如果分比左邊低，就只給一顆。

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:

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?

貪心法 復(fù)雜度

時間 O(N) 空間 O(N)

思路

典型的貪心法，如果一個孩子比另一個孩子的分高，我們只多給1塊糖。我們可以先從左往右遍歷，確保每個孩子根他左邊的孩子相比，如果分高，則糖要多1個，如果分比左邊低，就只給一顆。然后我們再從右往左遍歷，確保每個孩子跟他右邊的孩子相比，如果分高則糖至少多1個（這里至少多1個的意思是，我們要取當(dāng)前孩子手里糖的數(shù)量，和其右邊孩子糖的數(shù)量加1，兩者的較大值）。

代碼

public class Solution {
    public int candy(int[] ratings) {
        if(ratings.length <= 1){
            return ratings.length;
        }
        int[] candies = new int[ratings.length];
        candies[0] = 1;
        // 先從左往右分糖，分?jǐn)?shù)較高的多拿一顆糖，分?jǐn)?shù)較少的只拿一顆糖
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i - 1]){
                candies[i] = candies[i - 1] + 1;
            } else {
                candies[i] = 1;
            }
        }
        int sum = candies[candies.length - 1];
        // 再從右往左繼續(xù)分糖，分?jǐn)?shù)較高的確保比右邊多一顆就行了
        for(int i = ratings.length - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
                candies[i] = Math.max(candies[i + 1] + 1, candies[i]);
            }
            sum += candies[i];
        }
        return sum; 
    }
}