aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-01 18:17:40 -0600
committerJack Sangdahl <[email protected]>2025-06-01 18:17:51 -0600
commitaa747515fc961ec25c6044344ce7f31fb46b0b80 (patch)
tree8dfad1202fd5d2cef94b715e5fc561a4ef6757f6
parentb462378ab20dd837a053eda06e9e691ea17bef72 (diff)
downloadleetcode-aa747515fc961ec25c6044344ce7f31fb46b0b80.tar.gz
leetcode-aa747515fc961ec25c6044344ce7f31fb46b0b80.zip
135. candy
-rw-r--r--candy.c65
1 files changed, 25 insertions, 40 deletions
diff --git a/candy.c b/candy.c
index 318aa2f..4afb5ae 100644
--- a/candy.c
+++ b/candy.c
@@ -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
}