【C++算法入门】贪心算法-分糖果问题

本题取自LeetCode 135题 分糖果问题

一 原题复现

有n个小孩，每个小孩对应一个rating

条件：每个小孩至少得到一颗糖，评分高的小孩要比相邻小孩多一颗糖

求：最少需要多少糖

二 思路分析

本题利用贪心算法，需要两次遍历贪心。左到右：右边比左边大时，右边糖=左边糖+1；右到左：左边比右边大时，左边糖=右边糖+1；取其每个位置对应的最大值，再求和。我们举个例子加以说明：ratings={1,2,3,2,1}，从左到右：candy={1,2,3,1,1}，从右到左：candy={1,1,3,2,1}，各个位置取最大值candy={1,2,3,2,1}。得到最后结果9。

三 代码实现

思路总体较为简单，各位动手试一试吧。