candy

candy

Greedy approach

I meet this problem from hackrank one years before, at that time I did not resolve it. We need to consider two directions for each person and give him some candys. Think each direcion seprerately. Each person, give hime a candys from left, and give him b candys from right. The minnum candys we should give hime is max(a,b). Otherwise, if you try to meet the condictions, some one will be given zero or less candys.

 1 class Solution {
 2 public:
 3     int candy(vector<int> &ratings) {
 4         int n = ratings.size();
 5         if ( n == 0 ) {
 6             return 0;
 7         }
 8         int l[n];
 9         int r[n];
10         memset(l,0,sizeof(l));
11         memset(r,0,sizeof(r));
12         l[0] = 1;
13         r[n-1] = 1;
14         for( int i = 1; i < n; i++ ) {
15             int j = (n-1)-i;
16             if ( ratings[i] > ratings[i-1] ) {
17                 l[i] = l[i-1]+1;
18             } else {
19                 l[i] = 1;
20             }
21             if ( ratings[j] > ratings[j+1] ) {
22                 r[j] = r[j+1]+1;
23             } else {
24                 r[j] = 1;
25             }
26         }
27         int sum = 0;
28         for ( int i = 0; i < n; i++ ) {
29             sum += max(l[i],r[i]);
30         }
31         return sum;
32     }
33 };

A better way

The solutions before needs two array, and actually only one is needed. The second time travel the ratings we can get the answer already.

 1 class Solution {
 2 public:
 3     int candy(vector<int> &ratings) {
 4         int n = ratings.size();
 5         int t[n];
 6         memset(t,0,sizeof(t));
 7         t[0] = 1;
 8         for ( int i = 1; i < n; i++ ) {
 9             if ( ratings[i] > ratings[i-1] ) {
10                 t[i] = t[i-1]+1;
11             } else {
12                 t[i] = 1;
13             }
14         }
15         int now  = 1;
16         int sum = max(1,t[n-1]);
17         for ( int i = n-2; i >= 0; i-- ) {
18             if ( ratings[i] > ratings[i+1] ) {
19                 now += 1;
20             } else {
21                 now = 1;
22             }
23             sum += max(now,t[i]);
24         }
25         return sum;
26     }
27 };

Loading Disqus comments...
Table of Contents