diff options
-rw-r--r-- | candy.c | 65 |
1 files changed, 25 insertions, 40 deletions
@@ -1,6 +1,5 @@ // 135. Candy -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * there are 'n' children standing in a line. each child is assigned a rating @@ -12,48 +11,34 @@ * candies to the children */ -int candy(int *ratings, int ratings_size) { - if (!ratings_size) - return 0; - int *a = (int *)malloc(sizeof(int) * ratings_size); - a[0] = 1; - for (int i = 1; i < ratings_size; i++) { - if (ratings[i - 1] < ratings[i]) - a[i] = a[i - 1] + 1; - else if (ratings[i - 1] == ratings[i]) - a[i] = 1; - else { - int j = i - 1, k = 1, n; - while (j < ratings_size - 1 && ratings[j] > ratings[j + 1]) - k++, j++; - if (a[i - 1] >= k) { - n = k - 1; - j = i; - while (j < i + k - 1) { - a[j] = n; - n--; - j++; - } - } else { - n = k; - j = i - 1; - while (j < i + k - 1) { - a[j] = n; - n--; - j++; - } - } - i = j - 1; +int candy(int *ratings, int ratingsSize) { + int candy = ratingsSize, i = 1; + while (i < ratingsSize) { + if (ratings[i] == ratings[i - 1]) { + i++; + continue; } + int peak = 0; + while (ratings[i] > ratings[i - 1]) { + peak++; + candy += peak; + i++; + if (i == ratingsSize) + return candy; + } + int valley = 0; + while (i < ratingsSize && ratings[i] < ratings[i - 1]) { + valley++; + candy += valley; + i++; + } + candy -= fmin(peak, valley); } - int ans = 0; - for (int i = 0; i < ratings_size; i++) - ans += a[i]; - return ans; + return candy; } int main() { int r1[] = {1, 0, 2}, r2[] = {1, 2, 2}; - printf("%d\n", candy(r1, 3)); // expect: 5 - printf("%d\n", candy(r2, 3)); // expect: 4 + printf("%d\n", candy(r1, ARRAY_SIZE(r1))); // expect: 5 + printf("%d\n", candy(r2, ARRAY_SIZE(r2))); // expect: 4 } |