One pass O(1) space Java solution


  • 2
    M

    public class Solution {
    public int candy(int[] ratings) {
    if (ratings == null || ratings.length == 0) {
    return 0;
    }
    int sum = 1, pre = 1, peakIdx = 0, peakNum = 1;

        for (int i = 1;i < ratings.length; i++) {
            if (ratings[i] == ratings[i - 1]) {
                sum += 1;
                pre = 1;
                peakIdx = i;
                peakNum = 1;
            } else if (ratings[i] > ratings[i - 1]) {
                sum += pre + 1;
                peakIdx = i;
                peakNum = pre + 1;
                pre++;
            } else {
                if (pre == 1) {
                    if (i - peakIdx < peakNum) {
                        sum += i - peakIdx;
                    } else {
                        sum += i - peakIdx + 1;
                        peakNum++;
                    }
                } else {
                    sum += 1;
                    pre = 1;
                }
            }
        }
        
        return sum;
    }
    

    }


  • 0
    X

    very clever!


  • 0
    W

    good solution!


Log in to reply
 

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