社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
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:
What is the minimum candies you must give?
N个小孩站成一列.每个小孩都有一个分数.
你按照以下的规则,把这些糖果分给这些小孩:
1. 每个小孩至少有一个糖.
2.得分高的小孩比他的邻居小孩有更多的糖果.
你能分出的最少的糖果的数目是多少.
* 根据题意,思路可以如下:
* 初始化数组dp,数组成员均为1,每个孩子先分配一个糖果
* 从左向右遍历,如果第i个孩子比第i - 1孩子等级高,则dp[i] = dp[i - 1] + 1
* 从右向左遍历,如果第i个孩子比第i + 1孩子等级高并且糖果比i+1糖果少,则dp[i] = dp[i + 1] + 1
* 这种思路实现的算法复杂度为O(n)
整体思路图如下参考博客http://blog.csdn.net/lanxu_yy/article/details/17752273
<span style="font-family:Microsoft YaHei;font-size:10px;">public class Solution
{
public int candy(int[] ratings)
{
if (ratings == null || ratings.length == 0)
return 0;
ArrayList<Integer> dp = new ArrayList<Integer>();
for (int i = 0; i < ratings.length; i++)
dp.add(i, 1);
for (int i = 1; i < ratings.length; i++)
if (ratings[i] > ratings[i - 1])
dp.set(i, dp.get(i - 1) + 1);
for (int i = ratings.length - 2; i >= 0; i--)
if (ratings[i] > ratings[i + 1] && dp.get(i) <= dp.get(i + 1))
dp.set(i, dp.get(i + 1) + 1);
int res = 0;
for (int i = 0; i < dp.size(); i++)
res += dp.get(i);
return res;
}
}</span>
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!