P201 分糖果

描述#

这个题目说的是，n 个小孩站成一条直线，每个小孩都有一个对应的评分。你要根据小孩的评分给他们发糖果，要求每个小孩至少要有一个糖果，并且评分较高的小孩要比相邻的小孩分到更多糖果。你要计算出，至少需要准备多少颗糖果，才能按要求完成分配。

比如说，给你的小孩评分数组是：
[3, 3, 1, 6, 4, 3]
你最少要给这 6 个小孩分配的糖果数量是：
[1, 2, 1, 3, 2, 1]
按照这种分配方法，就可以达到题目要求。因此最少要准备的糖果数量就是这个数组的和，也就是 10。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public int candy(int[] ratings) {
    if (ratings == null || ratings.length == 0) return 0;
    int n = ratings.length;
    int[] d = new int[n];
    d[0] = 1;
    for (int i = 1; i < n; ++i) {
      if (ratings[i] > ratings[i-1])
        d[i] = d[i-1] + 1;
      else
        d[i] = 1;
    }
    int sum = d[n-1];
    for (int i = n-2; i >= 0; --i) {
      if (ratings[i] > ratings[i+1])
        d[i] = Math.max(d[i], d[i+1] + 1);
      sum += d[i];
    }
    return sum;
  }

}