Shorter O(n) Java solution base on exist solution


  • 0

    My solution is same as the most of the solution -- traverse the ratings twice, from start to end and from end to start. So two for loops are enough.

    public int candy(int[] ratings) {
            int[] candy = new int[ratings.length];
            candy[0] = 1;
            for(int i = 1; i < candy.length; i++){
                if(ratings[i] > ratings[i - 1]){
                    candy[i] = candy[i - 1] + 1;
                }else {
                    candy[i] = 1;
                }
            }
            int count = candy[candy.length - 1];
            for(int i = candy.length - 2; i >= 0; i--){
                if(ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]){
                    candy[i] = candy[i + 1] + 1;
                    
                }
                count += candy[i];
            }
            return count;
        }
    

Log in to reply
 

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