Joyce' Blog
0%

candy

发表于

题目描述

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

题解

先向左看，如果a[i]>a[i-1]，则有c[i]=c[i-1]+1；否则c[i]=1。再向右看，如果a[i]>a[i+1], 则有c[i]=(c[i], c[i+1]+1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int candy(vector<int>& ratings) {
	int num = ratings.size();
	int* ca = new int[num];
	for (int i = 0; i < num; i++)
		ca[i] = 1;
	for (int i = 1; i < num; i++)
		if (ratings[i] > ratings[i - 1])
			ca[i] = ca[i - 1] + 1;
	for (int i = num - 2; i >= 0; i--)
		if (ratings[i] > ratings[i + 1])
			ca[i] = max(ca[i], ca[i + 1] + 1);
	int res = 0;
	for (int i = 0; i < num; i++)
		res += ca[i];
	return res;
}

还有波峰波谷一次遍历的方法。