LeetCode | 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

  分析1

  可以先从左向右遍历一遍，保证如果右边小孩的rating大于左边邻居小孩，那么右边小孩的糖果也会多一个。

  再从右向左遍历一遍，保证如果左边小孩的rating大于右边邻居小孩，那么左边小孩的糖果要更大（多一个或本来就比右边小孩大）。

  通过两轮遍历，保证了每个孩子的糖果数和邻居相比都符合题目要求。

  这种做法的时间复杂度O(N)，空间复杂度O(N)。

  解法1

  public class Candy {
  	public int candy(int[] ratings) {
  		if (ratings == null || ratings.length <= 0) {
  			return 0;
  		}
  
  		int ret = 0;
  		int N = ratings.length;
  		int[] candy = new int[N];
  		candy[0] = 1;
  		for (int i = 1; i < N; ++i) {
  			candy[i] = 1;
  			if (ratings[i] > ratings[i - 1]) {
  				candy[i] = candy[i - 1] + 1;
  			}
  		}
  		ret = candy[N - 1];
  		for (int i = N - 2; i >= 0; --i) {
  			if (ratings[i] > ratings[i + 1]) {
  				candy[i] = Math.max(candy[i], candy[i + 1] + 1);
  			}
  			ret += candy[i];
  		}
  		return ret;
  	}
  }

  分析2

  还有一种只需要遍历一轮，并且空间复杂度O(1)的解法。

  在遍历过程中，通过纪录每个递减序列的大小和该序列中的最大糖果数，来不断更新总的糖果数。

  具体解释可以看http://oj.leetcode.com/discuss/76/does-anyone-have-a-better-idea这个链接中的best answer。

  解法2

  public class Candy {
  	public int candy(int[] ratings) {
  		if (ratings == null || ratings.length <= 0) {
  			return 0;
  		}
  
  		int ret = 1;
  		int seqLen = 0;
  		int preCandyCount = 1;
  		int maxCountInSeq = preCandyCount;
  		for (int i = 1; i < ratings.length; ++i) {
  			if (ratings[i] < ratings[i - 1]) {
  				++seqLen;
  				if (maxCountInSeq == seqLen) {
  					++seqLen;
  				}
  				ret += seqLen;
  				preCandyCount = 1;
  			} else {
  				if (ratings[i] > ratings[i - 1]) {
  					++preCandyCount;
  				} else {
  					preCandyCount = 1;
  				}
  				ret += preCandyCount;
  				seqLen = 0;
  				maxCountInSeq = preCandyCount;
  			}
  		}
  		return ret;
  	}
  }