Leetcode刷题随记 —— 135.分发糖果

文章目录

• • 题目
  • • 1. 题目描述
    • 2. 原题链接
    • 3. 样例输出
    • 4. 原题框架
  • 思路
  • 题解

题目 1. 题目描述

一群孩子站成一排，每一个孩子有自己的评分。

现在需要给这些孩子发糖果，如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果。

求解最少需要多少个糖果。

2. 原题链接

135.分发糖果

3. 样例输出

输入：

ratings = [1,0,2]

输出：

5

4. 原题框架

class Solution {
public:
    int candy(vector<int>& ratings) {
        
    }

};

思路

这一题运用贪心策略就能写出来，只需要我们进行两次遍历即可。

首先从左向右，如果右边孩子的评分比左边高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；

再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。

题解

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        
        if(size<2) {
            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);
            }
        }

        return accumulate(num.begin(),num.end(),0);
    }
};