Simple Java, O(n) time, O(1) space


  • 0
    I
    /*
     * if ratings[i] = ratings[i-1], then give[i] = 1
     * if ratings[i] > ratings[i-1], then give[i] = give[i-1] + 1, give[i] only depends on give[i-1], use cur instead
     * if ratings[i] < ratings[i-1], then give[i] = 1, and
     *  suppose last peak is at p with pv candies given, if i-p < pv, sum += i-j, else sum += i-j+1.
     */
    public class Solution {
        public int candy(int[] ratings) {
            int ans = 1, cur = 1, p = 0, pv = 1, n = ratings.length;
            for (int i = 1; i < n; i++) {
                if (ratings[i] == ratings[i-1]) {
                    p = i;
                    ans += pv = cur = 1;
                } else if (ratings[i] > ratings[i-1]) {
                    p = i;
                    ans += pv = ++cur;
                } else {
                    cur = 1;
                    ans += i-p < pv ? i-p : i-p+1;
                }
            }
            return ans;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.