leetcode 135.分发糖果 贪心法求解 （c++版本）

题目描述

要点注意的点题目都明确说出来了，这里就不多说
我们关注的是怎么用贪心法求解问题
首先哈最少糖果数目，那就是极限的数量（恰好满足要求的数量）
再考虑相邻评分更高的孩子获得更多的糖果（那么需要看周围孩子的分数）比较重要的点不仅仅看周围孩子的分数，因为是来连续数组因此其他孩子的分数也在变相的影响其的糖果数量

首次的错误想法

我想着糖果数是由左右相邻的分数值导致的，那么只需要根据大小将其进行加一即可，尝试之后发现判断的条件很多有9中情况（果断放弃）

正确思路

是数组，那么我先左遍历，再右遍历进行糖果数量的修正，这样肯定是可以的
换个思路就简单了很多

代码实现

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candy_num(ratings.size(), 1);
        // 左遍历
        for(int i = 1; i < ratings.size(); i++)
        {
            if(ratings[i] > ratings[i-1])
            {
                candy_num[i] = candy_num[i-1] + 1;
            }
        }
        // 右遍历
        for(int j = ratings.size()-2; j>=0; j--)
        {
            if(ratings[j] > ratings[j+1])
            {
                candy_num[j] = max(candy_num[j], candy_num[j+1]+1);
            }
        }
        int sum = 0; // 进行累加
        for(int i = 0; i<candy_num.size(); i++)
        {
            sum += candy_num[i];
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28