程序分享--常见算法/编程面试题：分发糖果

关注我，持续分享逻辑思维&管理思维&面试题； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》， 《做好面试准备，迎接2024金三银四》。
或关注博主免费专栏【程序员宝典--常用代码分享】里面有大量面试涉及的算法或数据结构编程题。

-------------------------------------正文----------------------------------------

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：
1.每个孩子至少分配到 1 个糖果。
2.相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，也能满足题干中的两个条件。

-------------------------------------答案----------------------------------------

class Solution {
public:
    static int candy(vector<int>& ratings) {
        int len = ratings.size();
        vector<int> uplift(len,0);
        vector<int> downlift(len,0);
        int cd = 0;
        for(int i = 1;i < len;i++){
            if(ratings[i]>ratings[i-1]) {
                cd++;
            } else  {
                cd = 0;
            }
            uplift[i] = cd;
        }
        cd = 0;
        for(int i = len-2;i >= 0;i--){
            if(ratings[i]>ratings[i+1]) {
                cd++;
            } else {
                cd = 0;
            }
            downlift[i] = cd;
        }
        cd = len;
        for(int i = 0;i < len;i++){
            cd += max(uplift[i],downlift[i]);
        }
        return cd;
    }
};

感兴趣的同学辛苦 关注/点赞 ，持续分享逻辑、算法、管理、技术、人工智能相关的文章。

博主其它经典原创：《管理心得--如何高效进行跨部门合作》，《技术心得--如何成为优秀的架构师》、《管理心得--如何成为优秀的架构师》、《管理心理--程序员如何选择职业赛道》，及
《C#实例：SQL如何添加数据》，《C#实战分享--爬虫的基础原理及实现》欢迎大家阅读。