题目描述
贪心思路
思路及解法
我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。
左规则：当 ratings[i−1]<ratings[i] 时，i 号学生的糖果数量将比 i−1 号孩子的糖果数量多。
右规则：当 ratings[i]>ratings[i+1] 时，i 号学生的糖果数量将比 i+1 号孩子的糖果数量多。
我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。
具体地，以左规则为例：我们从左到右遍历该数组，假设当前遍历到位置 i，如果有 ratings[i−1]<ratings[i] 那么 i 号学生的糖果数量将比 i−1 号孩子的糖果数量多，我们令 left[i]=left[i−1]+1 即可，否则我们令 left[i]=1。
在实际代码中，我们先计算出左规则 left 数组，在计算右规则的时候只需要用单个变量记录当前位置的右规则，同时计算答案即可。
作者：力扣官方题解
我们怎么知道，这两个规则得出来的结果，就能得出正确的答案呢？
首先满足左规则的情况下：
1 .只有当右边的数比左边的数大的时候右边的数始终比左边的数大1。
2. 当ratings[i]的数比ratings[i-1]的数小于等于的时候，此时所有的candies[i]都是1
满足右规则：
3. ratings[i] > ratings[i+1]时，candies[i]始终比candies[i+1]大1。
4. ratings[i] <= ratings[i+1]时, 这时候为了满足右规则和左规则，比较1和candies[i]取最大值来同时满足右边和左边。
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1);
// 从前向后
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}
// 从后向前
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] ) {
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
}
}
// 统计结果
int result = 0;
for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
return result;
}
};时间复杂度O(N)
空间复杂度O(N)
举例，关键步骤是同时满足左右两边，取最大值！
· ratings数组（上）左规则，右规则，candies数组(最下)
| 1 | 2 | 87 | 87 | 87 | 2 | 1 |
| 1 | 2 | 3 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 3 | 2 | 1 |
| 1 | 2 | 3 | 1 | 3 | 2 | 1 |
