O(n) time O(1) space accepted


  • 0
    T

    It's a mess, if I have time I will make it easier to understand and add some comment. The idea is the same as scan from start to end and end to start. But in a smater way.

    public class Solution {
        public int candy(int[] ratings) {
            int l = ratings.length;
            if(l <= 1)
                return l;
            int i = 0;
            int sum = 1;
            int add = 1;
            int check = 0;
            int top = 1;
            boolean ctop = false;
            while(check == 0 && i + 1 < l){
                if(ratings[i] < ratings[i + 1]){
                    check = 1;
                    add++;
                    top = add;
                    ctop = true;
                }
                else if(ratings[i] > ratings[i + 1]){
                    check = -1;
                    add++;
                }
                sum += add;
                i++;
            }
     
            for(i = i + 1; i < l; i++){
                if (ratings[i] == ratings[i - 1])
                {
                    check = 0;
                    add = 1;
                    ctop = false;
                }
                else if(check > 0 && ratings[i] < ratings[i - 1])
                    {
                        top = add;
                        ctop = true;
                        System.out.println("top = " + top + "\n");
                        add = 1;
                        check = -1;
                    }
                else if(check < 0 && ratings[i] > ratings[i - 1])
                {
                    add = 2;
                    check = 1;
                }
                else if(ratings[i] < ratings[i - 1]){
                    check = -1;
                    add++;
                    if(add >= top && ctop) {
                        add ++;
                        ctop = false;
                    }
                }
                else if(ratings[i] > ratings[i - 1]) {
                    check = 1;
                    add++;
                }
                sum += add;
            }
            return sum;
        }
    }
    

Log in to reply
 

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