4

leetcode 135. 分发糖果

 3 years ago
source link: https://iamxcb.com/leetcode-135.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

leetcode 135. 分发糖果

发表于 2019-07-29

| 0

| 阅读次数:

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：

  1. 每个孩子至少分配到 1 个糖果。
  2. 相邻的孩子中，评分高的孩子必须获得更多的糖果。
  3. 那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

首先初始化数组 candies 为 1（每个孩子分一个糖果），因为相邻的评分高的孩子可以获得更多的糖果，所以可以比较第 i 个孩子的分数 ratings[i] 是否比左边 ratings[i-1] ，右边 ratings[i+1] 高，如果比左边高则 candies[i] = candies[i-1] + 1 多给一颗糖果，比右边高则 candies[i] = max(candies[i], candies[i+1] + 1) (因为要同时保证比左右两边孩子的糖果数都高才行)

示例代码(go)

func candy(ratings []int) int {
    res, n := 0, len(ratings)
    candies := make([]int, n)
    for i := 0; i < n; i++ {
        candies[i] = 1
    }
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }
    for i := n-2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            candies[i] = max(candies[i], candies[i+1] + 1)
        }
    }
    for _, v := range candies {
        res += v
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK