Question

Formatted question description: https://leetcode.ca/all/135.html

135	Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

	Each child must have at least one candy.
	Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Algorithm

First initialize one candy for each person, and then the algorithm needs to traverse twice

  • the first traverse from left to right, if the level of the small pot on the right is high, one more candy to be added, which ensures that there are more candies in left-to-right direction.
  • Then it traverses from right to left again. If the two adjacent left sides have a higher level and the left side has fewer candies, the number of candies on the left is the number of candies on the right plus one. Finally, add up the number of candies of all the friends

My idea is to use four test cases: ratings:

  1. Monotonous increase: 7,8,9
  2. Monotonic reduction: 9,8,7
  3. Wave shape: 7,8,9,8,7
  4. Wave trough shape: 9,8,7,8,9

Code

Java

public class Candy {

	public class Solution {
	    public int candy(int[] ratings) {

	        int sum = 0;

	        if (ratings == null || ratings.length == 0) {
	            return sum;
	        }

	        int[] candies = new int[ratings.length];

	        // scan from left, and then scan from right
	        for (int i = 1; i < ratings.length; i++) {
	        	// start from 2nd element

	        	if (ratings[i] > ratings[i - 1]) {
	        		candies[i] = candies[i] < candies[i - 1] + 1 ? candies[i - 1] + 1 : candies[i];

	        	}
	        }

	        for (int i = ratings.length - 2; i >= 0; i--) {
	        	// also, start from 2nd last

	        	if (ratings[i] > ratings[i + 1]) {
	        		candies[i] = candies[i] < candies[i + 1] + 1 ? candies[i + 1] + 1 : candies[i];
	        	}
	        }

	        for (int each: candies) {
	        	sum += each;
	        }

	        return sum + ratings.length; // at least one candy for each
	    }
	}

}

All Problems

All Solutions