def candy(a: List[int]): if not a: return 0 res = 1 prev_candy = 1 descent_len = 1 descent_top = 1 for i, cur in enumerate(a[1:]): prev = a[i] if cur < prev: descent_len += 1 res += descent_len - 1 if descent_top < descent_len: descent_top += 1 res += 1 prev_candy = 1 else: if cur == prev: prev_candy = 1 else: prev_candy += 1 res += prev_candy descent_len = 1 descent_top = prev_candy return res
Explanation (cur and prev relate to the rates):
- cur == prev: give cur 1
- cur > prev : give cur what prev got + 1
- cur < prev : give cur 1, and an extra 1 to all prevs on the current slope except the top (first) one. The top one minimal size is the slope length, therefore it should be incremented only it it’s less than the slope length.