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

繁依Fanyi

发布于 2023-05-07 17:31:08

850

发布于 2023-05-07 17:31:08

文章被收录于专栏：繁依Fanyi 的专栏

题目

1. 题目描述

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

2. 原题链接

135.分发糖果

3. 样例输出

输入：

ratings = [1,0,2]

输出：

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);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-04-05，如有侵权请联系 cloudcommunity@tencent.com 删除

int