135. Give out candy

Topic describes

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.

Example 1:

Input: [1,0,2] Output: 5 Explanation: You can give two, one, two sweets to each of the three children.Copy the code

Example 2:

Input: [1,2,2] Output: 4 Explanation: You can give 1,2, 1 candy to each of the three children. The third child received only one candy, which satisfied both conditions.Copy the code

I tried to use object-oriented thinking to analyze the problem in a simple way, first providing a solution that could pass the test case, then gradually optimizing the code to find the most efficient solution. Since the title takes “children” as the “natural object” as the carrier, we will first give him a few new children. Since the title conditions require that “each child should be allocated at least 1 candy”, we will first give each child a candy. First define the Child class

class Child {
    constructor(rating) {
        / / score
        this.rating = rating;
        // In the initial case, each person has a candy in his hand
        this.candy = 1;
    }

    // Specify the number of sweets
    setCandy(n) {
        this.candy = n; }}Copy the code

Assumptions in ginsengratingsfor,3,4,5,2 [1]We are now going to divide the candy. The initial state is as follows:The question requires us to take into account both sides of the score of each child, so we can follow the greedy strategy and only consider and update the size relationship of the adjacent side in each traversal. That is, we need to traverse from the left and right sides respectively once to complete the process of dividing sugar. So, we break down “the child who scores higher must get more candy than the child on either side of him” into two strategies:

  1. Starting with the second child from the left, iterate over each child to the right. If the child πŸ‘ΆπŸ» scores higher than the child πŸ‘ˆ on the left, update the number of candies in the hand of πŸ‘Ά Doctor to the number of candies on the left +1

Why start with the second child and not the first? And that’s because the whole point of walking from left to right is that the kid who scored higher has more candy in his hand than the kid on his left, and the first kid has no one on his left, so he doesn’t have to participate in this walk. Let’s ignore strategy 2 and run through the program to see what happens: child 2:Third child:Fourth child:Fifth child:

Now all of the kids who scored higher had more sugar than the kid on the left. Now let’s look at the strategy on the other side.

  1. Starting from the second child on the right, each child is passed to the left. If πŸ‘ΆπŸ» scores higher than πŸ‘‰ on his right, and if the number of candies in the hand of πŸ‘Ά Doctor is equal to or less than the number of candies in the hand of πŸ‘Ά Doctor, the number of candies in the hand of πŸ‘Ά Doctor is changed to the number of candies in the hand of the child on the right +1

Similarly, there is no one to the right of the last child, so he doesn’t need to participate in the walk, so we just start with the second child from the right. Notice the bold part in this strategy, because after the last iteration, the child with a higher score might already have more sugar than the child on his right, so there’s no need to update his sugar count.

At this point, we complete the distribution process, and finally add up the number of sweets in each child’s hand to get the answer. The code is as follows:

class Child {
    constructor(rating) {
        this.rating = rating;
        this.candy = 1;
    }

    setCandy(n) {
        this.candy = n; }}var candy = function(ratings) {
    const children = ratings.map(rating= >{
        return new Child(rating);
    });

     // If the child has a higher score than the child on his left, then the child on the left has +1
    for (let i = 1; i < children.length; i++) {
        let left = children[i - 1];
        let kid = children[i];
        if (kid.rating > left.rating) {
            kid.setCandy(left.candy + 1); }}// If the child has a higher score than the child on the right, and the number of sweets in his hand is equal to or less than the child on the right, then the number of sweets in his hand is updated to the child on the right +1
    for (let i = children.length - 2; i >= 0; i--) {
        let right = children[i + 1];
        let kid = children[i];
        if (kid.rating > right.rating && kid.candy <= right.candy) {
            kid.setCandy(right.candy + 1); }}let res = 0;
    children.forEach(kid= >{
        res += kid.candy;
    })
    return res;
};
Copy the code

But the code above is clearly designed for visualization, including four walks through the array and introducing additional objects that take longer to execute and take up more memory. How inefficient is it? Just look at the picture below.First, since the Child class is specially designed for visualization, we can directly replace it with two arrays to save memory space. Moreover, since there are no additional objects, There is no need to convert the data type again, saving another traversal.

var candy = function(ratings) {
    const len = ratings.length;
    const candy = new Array(len).fill(1);

    // If the child has a higher score than the child on his left, then the child on the left has +1
    for (let i = 1; i < len; i++) {
        let kid = ratings[i];
        let left = ratings[i - 1];
        if (kid > left) {
            candy[i] = candy[i - 1] + 1; }}// If the child has a higher score than the child on the right, and the number of sweets in his hand is equal to or less than the child on the right, then the number of sweets in his hand is updated to the child on the right +1
    for (let i = len - 2; i >= 0; i--) {
        let kid = ratings[i];
        let right = ratings[i + 1];
        if (kid > right && candy[i] <= candy[i + 1]) {
            candy[i] = candy[i + 1] + 1; }}let res = 0;
    candy.map(candy= >res += candy);
    return res;
};

Copy the code

Well, the efficiency has been improved quite a bit, but if you look at it carefully, you can actually save on the last iteration of the traversal for summing up. Consider the following:

  1. After the first allocation traversal, we have an array of candy numbers, and the second allocation traversal is an adjustment of the array, modifying the numbers that do not meet the requirements
  2. As can be seen from the previous analysis, the first child does not participate in the first traversal allocation, and the last child does not participate in the second traversal allocation, so before the second traversal allocation, we can first giveresAssign the number of sweets to the last child as the initial value
  3. The accumulation occurs after the adjustment in the second walk, so it is perfectly possible to do this process together in the second walk rather than through it separately

From this, we can continue to optimize our code to look like this:

var candy = function(ratings) {
    const len = ratings.length;
    const candy = new Array(len).fill(1);

    // If the child has a higher score than the child on his left, then the child on the left has +1
    for (let i = 1; i < len; i++) {
        let kid = ratings[i];
        let left = ratings[i - 1];
        if (kid > left) {
            candy[i] = candy[i - 1] + 1; }}// The last child does not participate in the second allocation, so it can be directly assigned to res as the initial value
    let res = candy[candy.length - 1];
    
    // If the child has a higher score than the child on the right, and the number of sweets in his hand is equal to or less than the child on the right, then the number of sweets in his hand is updated to the child on the right +1
    for (let i = len - 2; i >= 0; i--) {
        let kid = ratings[i];
        let right = ratings[i + 1];
        if (kid > right && candy[i] <= candy[i + 1]) {
            candy[i] = candy[i + 1] + 1;
           
        }
         res += candy[i]
    }
    return res;
};
Copy the code

Now we save another iteration and look at the execution report, and the execution efficiency is much better than the previous one.This is my greedy strategy for the problem, from the concrete to the abstract, from the shallow to the deep, gradually optimize the code of the whole process, of course, if you use other methods may get better execution efficiency, and less memory, of course, that is a different perspective, I will not discuss in this article.