[LeetCode] 135. Candy (JS)

內容目錄 隱藏

題目

有 n 個孩子排成一排，陣列 ratings 中代表每個孩子的分數，你可以送這些小朋友糖果，但需符合以下要求：

每個孩子必須至少擁有一顆糖果。
得分較高的孩子比旁邊的孩子要獲得更多醣果。

返回分給孩子們所需的最少糖果數量。

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

解題思路

每個孩子需要和左右兩邊的小孩比較，如果同時和左右邊比較很容易出錯，所以可以分開比較。

分別確認：

右邊的小孩比左邊的小孩得分高
左邊的小孩比右邊的小孩得分高
取最大值即為每個孩子被分發的最少糖果數

ratings: [1,2,2,5,4,3,2]
=>candy_left: [1,2,1,2,1,1,1] // 1.右邊的小孩比左邊的小孩得分高
=>candy_right: [1,1,1,4,3,2,1] // 2.左邊的小孩比右邊的小孩得分高
=>candy: [1,2,1,4,3,2,1] // 3.取最大值

程式碼

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let candy = new Array(ratings.length).fill(1)
    // 1. 只看右比左大的情況，前至後遍歷
    for (let i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candy[i] = candy[i - 1] + 1
        }
    }
    // 2. 只看左比右大的情況，後至前遍歷
    for (let i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candy[i] = Math.max(candy[i + 1] + 1, candy[i])
        }
    }
    return candy.reduce((acc, cur) => acc + cur, 0)
};

瀏覽量: 12