Candy
- From left to right, to make all candies satisfy the condition if ratings[i] > ratings[i - 1] then candies[i] > candies[i - 1], just ignore the right neighbor as this moment. We can assume leftCandies[i] is a solution which is satisfied.
- From right to left, almost like step 1, get a solution rightCandies[i] which just satisfy the condition if ratings[i] > ratings[i + 1] then candies[i] > candies[i + 1]
For now, we have leftCandies[i] and rightCandies[i], so how can we satisfy the real condition in the problem? Just make candies[i] equals the maximum betweenleftCanides[i] and rightCandies[i]
即把整个过程分为两个步骤，第一步从左到右，只要右边的ratings大于自己，右边的糖数量就＝自己+1, (先不管左边大于右边的情况)，这一步完成之后有条件,ratings[i] > ratings[i - 1] && candies[i] > candies[i - 1] 然后再从右往左，一样的思路，使得ratings[i] > ratings[i + 1] && candies[i] > candies[i + 1]。 最后candies再取两个中的max，这样就同时满足这两个条件。问题解决。
int candy2(vector<int> &ratings) { int n = ratings.size(); if(n <= 1) return n; vector<int> candies(n, 1); //left to right for(int i = 1; i < n; i++) { if(ratings[i] > ratings[i-1]) candies[i] = candies[i-1]+1; else candies[i] = 1; } int total = candies[n-1]; for(int i = n-2; i >= 0; i--) { if(ratings[i] > ratings[i+1]) candies[i] = std::max(candies[i+1]+1, candies[i]); total += candies[i]; } return total; }