[LintCode/LeetCode] Candy

baishancloud 發(fā)布于2019-08-14 15:43 / 3548人閱讀

摘要：保證高的小朋友拿到的糖果更多，我們建立一個分糖果數(shù)組。首先，分析邊界條件如果沒有小朋友，或者只有一個小朋友，分別對應(yīng)沒有糖果，和有一個糖果。排排坐，吃果果。先往右，再往左。右邊高，多一個。總和加上小朋友總數(shù)，就是要準(zhǔn)備糖果的總數(shù)啦。

Problem

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

Given ratings = [1, 2], return 3.

Given ratings = [1, 1, 1], return 3.

Given ratings = [1, 2, 2], return 4. ([1,2,1]).

Note

保證rating高的小朋友拿到的糖果更多，我們建立一個分糖果數(shù)組A。小朋友不吃糖果，考試拿A也是可以的。
首先，分析邊界條件：如果沒有小朋友，或者只有一個小朋友，分別對應(yīng)沒有糖果，和有一個糖果。
然后我們用兩個for循環(huán)來更新分糖果數(shù)組A。
排排坐，吃果果。先往右，再往左。右邊高，多一個。左邊高，吃得多。
這樣，糖果數(shù)組可能就變成了類似于[0, 1, 0, 1, 2, 3, 0, 2, 1, 0]，小朋友們一定看出來了，這個不是真正的糖果數(shù)，而是根據(jù)考試級別ratings給高分小朋友的bonus。
好啦，每個小朋友至少要有一個糖果呢。
bonus總和加上小朋友總數(shù)n，就是要準(zhǔn)備糖果的總數(shù)啦。

Solution

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n < 2) return n;
        int[] A = new int[n];
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1]) A[i] = A[i-1]+1;
        }
        for (int i = n-2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) A[i] = Math.max(A[i], A[i+1]+1);
        }
        int res = n;
        for (int a: A) res += a;
        return res;
    }
}