分糖

N个孩子站成一排,给每个人设定一个权重。按照如下规则分配糖果:

1)每个孩子至少分的一个糖果

2)权重高的孩子,会比他的邻居获得更多的糖果

问:总共最少需要多少颗糖果?分析算法思路,算法时间、空间复杂度?

思路:

假设每个孩子分到的糖果数组为A[N],初始化为{1},因为每个人至少分到一颗糖。

1、与前面的邻居比较,前向遍历权重数组ratings,如果ratings[i] > ratings[i-1],则A[i] = A[i-1]+1;

2、与后面的邻居比较,后向遍历权重数组ratings,如果ratings[i] > ratings[i+1]且A[i] <= A[i+1]+1,则更新A,A[i]=A[i+1]+1;

3、对A求和即为最少需要的糖果。

时间复杂度O(n)、空间复杂度O(n)。

// 贪心法
class Solution {
	public int candy(int[] ratings){
		
		int sum = 0;
		if(ratings == null||ratings.length == 0){
			return 0;
		}
		int[] count = new int[ratings.length];
		Arrays.fill(count, 1);
		for(int i = 1; i < ratings.length; i++){
			if(ratings[i-1]	< ratings[i]){
				count[i] = count[i-1]+1;
			}
		}
		for(int i = ratings.length-1; i > 0; i++){
			sum += count[i];
			if(ratings[i] < ratings[i-1]&&count[i] >= count[i-1]){
				count[i-1] = count[i]+1;
			}
		}
		sum += count[0];
		return sum;
	}
}

 

上一篇:LeetCode 135. 分发糖果(DP)


下一篇:数据分析实例-MovieLens 1M 数据集