candy
需要将git的workspace移到hexo目录下才可以 hexo new ‘post’ 来生成新的.md文件。。。
leetcode一道candy题目，大意是每个小孩有打分，至少都有1个糖果，且比两个邻居(如果有的话)打分高的话要比邻居糖果多，求总的糖果至少多少？
我分析了之后，发现题目不明确，如果邻居相等的话，不知道多少，如果小于的话也没有说。这个先放下，一般是先分析general的情况。
一遍是不行的，因为可能后面降的时候，不知道降多少，可能不是decrease 1的降. 然后我在想，从前往后，再从后往前，其实有个解法是这样的，但我没有继续这么想。我想到的做法是，先把这些极小值点找出来，然后往上爬着增一定不会错，但是注意覆盖极大值的时候，可能被赋值两次，
于是要选择两者中较大的，打擂台完成。
先一遍遍历找极小值，然后后面遍历这个极小值index的数组，每个从两边(如果有的话)往上爬，直至极大值点。但是其实如果1 1 1 1 2 2 2 1 1 1 我就不清楚那些2应该给多少candy了，按道理的话他们都不满足比
两个邻居大，应该可以赋1的，但是我算出来是 2 1 2，结果还AC了，我感觉题目说不清楚。。。如果测试用例包含的情况足够的话。。。
最怕这种连题意都没完全理清楚，好像也没完全说清楚，但是又糊里糊涂的过了。。。
后来发现这位仁兄，非常简洁的两边扫描就完成了，往上增，右边也往上增，初始为1，比我的简洁多了。
http://zhaohongze.com/wordpress/2013/12/10/leetcode-candy/
int candy(vector<int>&ratings)
{
int *candy=new int[ratings.size()]();//candy number of each child
for(int i=0;i<ratings.size();i++)//initial 1, as some child that are not bigger than neighbors, but one bigger, one equal also one, not clear
candy[i]=1;
//memset(candy,1,sizeof(int)*ratings.size());//this can not memset, as memeset fill Bytes with 1, which make 0001000100010001(hex) like this, which is wrong, so memset can only zero(clear)
//get min array
vector<int> minvec;//min ratings array
//int *minvec=new int[ratings.size()];
int k;
//create min index array
for(int i=0;i<ratings.size();i++)
{
if(i-1>=0 && i+1 <= (ratings.size()-1) )
{
if(ratings.at(i-1) >= ratings.at(i) && ratings.at(i)<=ratings.at(i+1))//<= include equal or less than
{
//minvec[k]=i;
candy[i]=1;
//k++;
minvec.push_back(i);
}
}
else if( i-1 >= 0 && i+1 > (ratings.size()-1))
{
if(ratings.at(i-1) >= ratings.at(i))
{
candy[i]=1;
minvec.push_back(i);
}
}
else if( i-1 < 0 && i+1 <= (ratings.size()-1) )
{
if(ratings.at(i)<=ratings.at(i+1))
{
candy[i]=1;
minvec.push_back(i);
}
}
}
//from min to two side increase
for(int i=0;i<minvec.size();i++)
{
int j=minvec.at(i),k=j;
while(j>=1 && ratings.at(j-1) > ratings.at(j))//equal would be as inital value, 1
{
if(candy[j-1] < candy[j]+1)//get max of two value
candy[j-1]=candy[j]+1;
j--;
}
j=k;
while(j<=ratings.size()-2 && ratings.at(j) < ratings.at(j+1))
{
if(candy[j+1] < candy[j] +1)
candy[j+1]=candy[j]+1;
j++;
}
}
int mincandy=0;
for(int i=0;i<ratings.size();i++)
{
cout<<candy[i]<<" ";
mincandy+=candy[i];
}
cout<<endl;
//delete [] minvec;
delete [] candy;
return mincandy;
}