Candy@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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，然后两边开始增加。但这样code社会会很复杂。

看到discuss有一个很好的做法，就是两头扫瞄，第一次从左到右，第二次从右到左，这样递增和递减的关系就刚好相反。每一个递增都加一，递减就不变。注意边界条件的判断会导致所有位置都少加了一个1，所以结果要加上数列的长度。

	class Solution {
	public:
	int candy(vector<int> &ratings) {
	// Note: The Solution object is instantiated only once and is reused by each test case.
	if(ratings.empty()) return 0;
	vector<int> val(ratings.size(), 0);
	int k=0, i=0;
	for(k=1, i=0; i<ratings.size(); i++)
	{
	if((i-1)>=0&&ratings[i]>ratings[i-1])
	val[i] = std::max(k++,val[i]);
	else
	k=1;
	}
	for(k=1, i=ratings.size()-1; i>=0; i--)
	{
	if((i+1)<ratings.size()&&ratings[i]>ratings[i+1])
	val[i] = std::max(k++,val[i]);
	else
	k=1;
	}
	int sum=ratings.size();
	for(i=0; i<ratings.size(); i++)
	{
	sum+=val[i];
	}
	return sum;
	}
	};

view raw Candy hosted with ❤ by GitHub