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.
Solution: scan twice: find out the inversion and correct the number of candies for the corresponding child.
class Solution { public: int candy(vector<int> &ratings) { // Note: The Solution object is instantiated only once and is reused by each test case. int n = ratings.size(); vector<int> res(n, 1); if(n==0) return 0; for(int i=1; i<n; ++i){ if(ratings[i]>ratings[i-1]) res[i] = res[i-1]+1; } for(int i=n-2; i>=0; --i){ if(ratings[i]>ratings[i+1] && res[i]<=res[i+1]) res[i] = res[i+1]+1; } int sum = 0; for(int i=0; i<n; ++i) sum+=res[i]; return sum; } };
No comments:
Post a Comment