[golang] 135. Candy

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// candy
//
// 135. Candy
// There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
//
// 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.
// Return the minimum number of candies you need to have to distribute the candies to the children.
//
// Example 1:
//
// Input: ratings = [1,0,2]
// Output: 5
// Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
// Example 2:
//
// Input: ratings = [1,2,2]
// Output: 4
// Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
// The third child gets 1 candy because it satisfies the above two conditions.
//
// Constraints:
//
// n == ratings.length
// 1 <= n <= 2 * 104
// 0 <= ratings[i] <= 2 * 104
func candy(ratings []int) int {
 
    // Length содержит длину массива ratings
    length := len(ratings)
 
    // Создаем слайс для подсчета и сравнения полученных конфет
    candies := make([]int, length)
 
    // Раздаем по конфете
    // Условие "Each child must have at least one candy."
    for i, _ := range candies {
        candies[i] = 1
    }
 
    // Обходим слайс слева направо до предпоследнего элемента
    for i := range length - 1 {
        // Если рейтинг текущего ребенка меньше рейтинга ребенка справа
        if ratings[i] < ratings[i+1] {
            // Ребенок справа получает на одну конфету больше чем есть у текущего ребенка
            candies[i+1] = candies[i] + 1
        }
    }
 
    // Обходим слайс справа налево до второго элемента
    for i := length - 1; i > 0; i-- {
        // Если у текущего ребенка рейтинг ниже чему у ребенка слева
        // и у конфет у текущего ребенка больше или столько же как у ребенка слева
        if ratings[i] < ratings[i-1] && candies[i] >= candies[i-1] {
            // У ребенка слева становится конфет больше на одну чем у текущего
            candies[i-1] = candies[i] + 1
        }
    }
 
    // Возвращаем сумму конфет
    sum := 0
    for _, n := range candies {
        sum += n
    }
    return sum
}

func TestCandy(t *testing.T) {
    data := []struct {
        ratings  []int
        expected int
    }{
        {
            []int{1, 0, 2},
            5,
        },
        {
            []int{1, 2, 2},
            4,
        },
        {
            []int{1, 3, 2, 2, 1},
            7,
        },
        {
            []int{1, 2, 87, 87, 87, 2, 1},
            13,
        }, {
            []int{1, 3, 4, 5, 2},
            11,
        },
    }
 
    for i, datum := range data {
        result := candy(datum.ratings)
 
        if result != datum.expected {
            t.Errorf("unexpected result for test index %d expected [%d] got [%d]", i, datum.expected, result)
        }
    }
}