Just one O(n) space O(1)


  • 0
    K
    public class Solution {
        public int candy(int[] ratings) {
            if (ratings==null||ratings.length==0) return 0;
            if (ratings.length==1) return 1;
            int res=0,downLen=0,preCandy=1,lastdownCandy=1;
            for (int i=1;i<ratings.length;i++){
                if (ratings[i]<ratings[i-1]){
                    downLen++;
                    if (lastdownCandy<=downLen) res++;
                    res+=downLen;
                    preCandy=1;
                }else {
                    if (ratings[i]>ratings[i-1]){
                        res+=++preCandy;
                        lastdownCandy=preCandy;
                    }else {
                        preCandy=1;
                        res+=preCandy;
                        lastdownCandy=preCandy;
                    }
                    downLen=0;
                }
            }
            return res+1;
        }
    }

Log in to reply
 

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