LeetCode题解–135. Candy

链接

LeetCode题目：https://leetcode.com/problems/candy/

难度：Hard

题目

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their >neighbors. What is the minimum candies you must give? 题目大意是N个小孩站成一排，每个小孩都被分配了一个分数。现在要给他们发糖，需要满足两个条件：一，每个小孩至少分到一块糖；二，分数高的小孩必须比他相邻的小孩分的糖多。求问最少需要发多少块糖？

分析

这题一开始想的是用贪心算法做，先给第一个小孩发1块糖。后面每加一个小孩站在右边，如果他的分数比左边的小孩高，给他比左边小孩发多1块糖；如果分数相等，只给他发1块糖；如果分数低，则是我们需要重点关注的情况，先给他发1块糖，然后向左回溯，检查每个小孩相比其右边小孩是否分数更高但糖不更多，如果是的话，给他发多1块糖。这个思路没问题，但因为时间复杂度是O(n^2)，不能通过最后一个测试用例。 重新思考了一下，其实不需要回溯。如果遇到的小孩连续都是分数比左边低的，这个分数子序列会变成一个递减序列，我们可以用max_pos记录这个递减序列最左边的位置，max_candy记录这个位置的小孩当前拿了几颗糖。这样一来，每次遇到第i个分数低的小孩，可以把[max_pos+1, i-1]这个区间的小孩发多1块糖，然后再判断max_pos位置的小孩是否需要多得1颗糖。

代码

class Solution { public: int candy(vector<int> &ratings) { int n = (int) ratings.size(); if (n == 0) return 0; vector<int> candies((unsigned long) n, 0); candies[0] = 1; int sum = 1; int max_pos = 0, max_candy = 1; for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; max_pos = i; max_candy = candies[i]; } else if (ratings[i] == ratings[i - 1]) { candies[i] = 1; max_pos = i; max_candy = 1; } else { candies[i] = 1; sum += i - max_pos - 1; if (max_candy < i - max_pos + 1) { max_candy = i - max_pos + 1; sum += 1; } } sum += candies[i]; } return sum; } };