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?
Solution: You may refer to
https://github.com/AnnieKim/ITint5/blob/master/031_%E5%88%86%E9%85%8D%E7%B3%96%E6%9E%9C.cpp
1. traverse only once with O(1) space. 2. O(n) space.
1 class Solution { 2 public: 3 int candy(vector<int> &ratings) { 4 int N = ratings.size(); 5 vector<int> candy(N,1); 6 for(int i = 1; i < N; i++) { 7 if(ratings[i] > ratings[i-1]) { 8 candy[i] = candy[i-1] + 1; 9 } 10 } 11 for(int i = N - 2; i >= 0; i--) { 12 if(ratings[i] > ratings[i+1] && candy[i] <= candy[i+1]) { 13 candy[i] = candy[i+1] + 1; 14 } 15 } 16 int res = 0; 17 for(int i = 0; i < N; i++) { 18 res += candy[i]; 19 } 20 return res; 21 } 22 };
原文：http://www.cnblogs.com/zhengjiankang/p/3676164.html