原题链接：https://leetcode.com/problems/candy/?tab=Description 135. Candy 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颗糖，分值比它旁边的人高的小孩得到的糖比旁边的人多，问：至少要给出多少糖？
这题需要注意的一个坑是：如果相邻的两个人分值是相同的，那么他们手里的糖不一定要相等，比如：如果分值的序列是这样的2 2 1，分配的糖果是1 2 1，而不是2 2 1.
我的思维是：先找出分值最少的小孩，给他一颗糖，然后左右分治，分别找出左右分值最少的小孩，如果找到的这个小孩的左右没有任何一个拿过糖，那么就给这个小孩一颗糖，否则，依据左右已经得到糖的孩子手里的糖的数量以及分值，决定这个孩子得到多少糖。 代码如下：
#include<iostream> #include<vector> #include<algorithm> using namespace std; class Solution { public: int* divide; int* formal; int full_num; int find_min(int *start, int num) { if (num <= 0) return -1; int a = *start; int id = 0; for (int i = 1; i < num; ++i) { if (a>*(start + i)) a = *(start + i), id = i; } return id; } void fenzhi(int *formal,int start, int num) { if (num <= 0) return; int index = find_min(formal + start, num) + start; if (index + 1 >= full_num) { if (*(divide + index - 1) == 0) *(divide + index) = 1; else if (*(formal + index - 1) == *(formal + index)) *(divide + index) = 1; else *(divide + index) = *(divide + index - 1) + 1; } else if (index - 1 < 0) { if (*(divide + index + 1) == 0) *(divide + index) = 1; else if (*(formal + index + 1) == *(formal + index)) *(divide + index) = 1; else *(divide + index) = *(divide + index + 1) + 1; } else if (*(divide + index + 1) == 0) { if (*(divide + index - 1) == 0) *(divide + index) = 1; else if (*(formal + index - 1) == *(formal + index)) *(divide + index) = 1; else *(divide + index) = *(divide + index - 1) + 1; } else if (*(divide + index - 1) == 0) { if (*(divide + index + 1) == 0) *(divide + index) = 1; else if (*(formal + index + 1) == *(formal + index)) *(divide + index) = 1; else *(divide + index) = *(divide + index + 1) + 1; } else { if (*(formal + index + 1) == *(formal + index)) { *(divide + index) = 1; if (*(formal + index - 1) < *(formal + index) && *(divide + index - 1) >= *(divide + index)) *(divide + index) = *(divide + index - 1) + 1; } else if (*(formal + index - 1) == *(formal + index)) { *(divide + index) = 1; if (*(formal + index + 1) < *(formal + index) && *(divide + index + 1) >= *(divide + index)) *(divide + index) = *(divide + index + 1) + 1; } else if (*(divide + index + 1) > *(divide + index - 1)) *(divide + index) = *(divide + index + 1) + 1; else *(divide + index) = *(divide + index - 1) + 1; } fenzhi(formal, start, index - start); fenzhi(formal, index + 1, num - index + start - 1); } int candy(vector<int>& ratings) { full_num = ratings.size(); divide = new int[full_num]; formal = new int[full_num]; for (int i = 0; i < full_num; ++i) *(divide + i) = 0; for (int i = 0; i < full_num; ++i) *(formal + i) = ratings[i]; if (full_num == 1) return 1; fenzhi(formal, 0, full_num); int sum = 0; for (int i = 0; i < full_num; ++i) { sum += *(divide + i); } delete [] formal; delete [] divide; return sum; } }; int main() { vector<int> ratings = { 1,3,4,3,2,1 }; Solution a; int outx = a.candy(ratings); cout << outx; getchar(); getchar(); return 0; }代码很长，时间成本很高，虽然可以通过leetcode的评测，但是这显然不是可以接受的方法，下面对评论区大神的代码做一些分析。
对于种左右比较的题目，分别对每个数的要求可以归纳为： 1. 如果当前孩子的分值比左边孩子高，他的糖果要比左边孩子多 2. 如果当前孩子的分值比右边孩子高，他的糖果要比右边孩子多
我的思维定式是，一个一个孩子去讨论，比如说我的思维定式就是从小到大往里填数据，但是更好的思维方式是：将上面的情况1作为一个大类讨论，情况2作为另一个情况讨论。 具体而言，先从左到右遍历一遍，确保当前孩子的分值比左边孩子高，他的糖果要比左边孩子多，再从右到左遍历一遍，确保当前孩子的分值比右边孩子高，他的糖果要比右边孩子多。
代码如下：
int candy(vector<int> &ratings) { int size=ratings.size(); if(size<=1) return size; vector<int> num(size,1); for (int i = 1; i < size; i++) { if(ratings[i]>ratings[i-1]) num[i]=num[i-1]+1; } for (int i= size-1; i>0 ; i--) { if(ratings[i-1]>ratings[i]) num[i-1]=max(num[i]+1,num[i-1]); } int result=0; for (int i = 0; i < size; i++) { result+=num[i]; // cout<<num[i]<<" "; } return result; }