文章目录
  1. 1. 贪心
  2. 2. 不需要辅助空间

【题目】: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?

贪心

用贪心法来做,我们用candy[n]表示每个孩子的糖果数,遍历过程中,如果孩子i+1的rate大于孩子i 的rate,那么当前最好的选择自然是:给孩子i+1的糖果数=给孩子i的糖果数+1。

如果孩子i+1的rate小于等于孩子i 的rate咋整?这个时候就不大好办了,因为我们不知道当前最好的选择是给孩子i+1多少糖果。

解决方法是:暂时不处理这种情况。等数组遍历完了,我们再一次从尾到头遍历数组,这回逆过来贪心,就可以处理之前略过的孩子。最后累加candy[n]即得到最小糖果数。

public int candy(int[] ratings) {
    int result = 0;
    if (ratings == null || ratings.length == 0) {
        return result;
    }
    int length = ratings.length;
    int[] candies = new int[length];

    for (int i=0; i<length; i++) {
        candies[i] = 1;
    }
    for (int i=1; i<length; i++) {
        if (ratings[i] > ratings[i-1])
            candies[i] = candies[i-1] + 1;
    }
    for (int i=length-1; i>0; i--) {
        if (ratings[i] < ratings[i-1]&& candies[i-1] <= candies[i])
            candies[i-1] = candies[i] + 1;
    }

    for (int i=0; i<length; i++) {
        result += candies[i];
    }

    return result;
}

需要O(n)的辅助空间给candy[]。

不需要辅助空间

边遍历边修正的方法可以保证一次遍历,不需要O(n)空间下计算出total的正确值。

public int candy(int[] ratings) {
    if (ratings == null || ratings.length == 0) {
        return 0;
    }

    int total = 1;
    int length = 0;
    int preCandies = 1;
    int preDenc = preCandies;


    for (int i=1; i<ratings.length; i++) {
        if (ratings[i] < ratings[i-1]) {
            length++;
            if (preDenc <= length) {
                total++;
            }
            total += length;
            preCandies = 1;

        } else {
            int currentCandy = 0;
            if (ratings[i] > ratings[i-1]) {
                currentCandy = preCandies + 1;
            } else {
                currentCandy = 1;
            }

            total += currentCandy;
            preCandies = currentCandy;
            length = 0;
            preDenc = currentCandy;
        }
    }

    return total;
}
文章目录
  1. 1. 贪心
  2. 2. 不需要辅助空间