这也是一个一维数组上面的动态规划问题

描述

有N个小朋友站在一排，每个小朋友都有一个评分
你现在要按以下的规则给孩子们分糖果：
每个小朋友至少要分得一颗糖果
分数高的小朋友要他比旁边得分低的小朋友分得的糖果多
你最少要分发多少颗糖果？

示例1

输入：
[1,2,2]
复制
返回值：
4

解题思路

仔细分析可以知道, 要找到这个数组中递增和递减的部分, 递增部分每次次加1, 递减部分, 从高到低每次减1
但是会出现这种

1, 2, 6, 5, 4, 3, 2,1 1, 2, 3, 4, 5, 6, 2,1

这两种情况, 这样处在峰值的数字的量就要是峰值两边数组的长度来算了
我们可以用初始化data[i]用于记录每一位的值, 初始化都为1
然后顺序遍历, 递增的是前一个+1
然后倒叙遍历, 递增的是后一个+1 与 自己本身值的最大值(因为峰值问题会出现)

代码

    int candy(vector<int>& ratings) {vector<int> data(ratings.size(), 1);for (int i = 1; i < ratings.size(); i++)if (ratings[i] > ratings[i - 1])data[i] = max(data[i], data[i - 1] + 1);for (int i = ratings.size() - 2; i >= 0; i--)if (ratings[i] > ratings[i + 1])data[i] = max(data[i], data[i + 1] + 1);int res = 0;for (int num : data)res += num;return res;}

时间还行, 空间可能仍需优化