135. Handing out candy (Difficulty: Difficulty)

The teacher wants to hand out candy to the children. There are N children standing in a straight line, and the teacher will score each child in advance according to their performance.

You need to help the teacher to distribute sweets to these children according to the following requirements:

Each child gets at least one candy. The child who scored higher had to get more candy than the child on either side of him. So how many candies should the teacher prepare?

Their thinking

  1. Initialize the candy count for all children to 1;
  2. If the child on the right scores higher than the child on the left, the number of sweets on the right is updated to the number of sweets on the left +1.
  3. If the child on the left has a higher rating than the child on the right, and the current number of sweets on the left is no greater than the number of sweets on the right, the number of sweets on the left is updated to the number of sweets on the right +1.

Answer key

public int findMinCandyCount(int[] ratings) {
    int childCount = ratings.length;

    int[] candy = new int[childCount];
    Arrays.fill(candy, 1);

    for (int index = 1; index < childCount; index++) {
        if (ratings[index - 1] < ratings[index]) {
            candy[index] = candy[index - 1] + 1; }}int minCount = 0;
    for (int index = childCount - 1; index > 0; index--) {
        if (ratings[index - 1] > ratings[index]) {
            candy[index - 1] = Math.max(candy[index - 1], candy[index] + 1);
        }
        minCount += candy[index];
    }
    minCount += candy[0];

    return minCount;
}
Copy the code

test

Candy candy = new Candy();

@Test
public void text_case1(a) {
    Assertions.assertEquals(5, candy.findMinCandyCount(new int[] {1.0.2}));
}

@Test
public void test_case2(a) {
    Assertions.assertEquals(4, candy.findMinCandyCount(new int[] {1.2.2}));
}

@Test
public void test_case3(a) {
    Assertions.assertEquals(3, candy.findMinCandyCount(new int[] {1.2}));
}

@Test
public void test_case4(a) {
    Assertions.assertEquals(1, candy.findMinCandyCount(new int[] {2}));
}
Copy the code