135. 分发糖果
两次遍历（贪心算法）
贪心策略：在每次遍历中，只考虑并更新相邻一侧的大小关系。
将相邻的孩子中，评分高的必须获得更多的糖果这句话拆分成2个规则
左规则：当ratings[i-1]<ratings[i]时，i号学生糖果数量比i-1号学生糖果数量多
右规则：当ratings[i]>ratings[i+1]时，i号学生糖果数量比i+1号学生糖果数量多
遍历数组2次，分别求满足左规则和右规则时，最少要分得的糖果数量。最终分得糖果数量即为这两个数量最大值。
class Solution { public: int candy(vector<int> &ratings) { vector<int> ans(ratings.size(), 1); int n = ans.size(); for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { ans[i] = ans[i - 1] + 1; } } for (int i = n - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { // 左规则和有规则取最大值 ans[i] = max(ans[i + 1] + 1, ans[i]); } } return accumulate(ans.begin(), ans.end(), 0); } };
一次遍历
图中，第3列可以看作是1，2，3（绿色部分）的递增序列，也可以看作是3，4，5（蓝色部分）的递减序列。
修改序列，现在第3列不得不是4个糖果了。
依照上面的规律：
如果当前同学比上一个同学评价高，那么说明我们在递增序列中，直接分配该同学的糖果比前一个同学多一即可。
否则在递减序列中，我们可以默认递减序列的末尾是1，所以实际上是从尾到头递增。直接分配给当前同学一个糖果，并把该同学所在递减序列所有同学再多分配一个糖果。
如果当前递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。如上图，第3列长度本为3，第4列长度也为3，按照定义，第4列评分<第3列评分，所以第3列长度大于第4列长度，因此第3列长度加1变为4。
class Solution { public: int candy(vector<int> &ratings) { int n = ratings.size(); int ret = 1, pre = 1, inc = 1, dec = 0; for (int i = 1; i < n; i++) { if (ratings[i] >= ratings[i - 1]) { dec = 0; pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1; ret += pre; inc = pre; } else { dec++; if (dec == inc) { dec++; } ret += dec; pre = 1; } } return ret; } };
