2022.01.01 - SX09-12.分发糖果

2022.01.01 - SX09-12.分发糖果

文章目录

• 1. 题目
• 2. 思路
• • (1) 贪心算法
• 3. 代码

1. 题目

2. 思路 (1) 贪心算法

• 首先将相邻孩子评分高的糖果更多拆分成两条规则：
  1. 左规则：若孩子比其左边孩子的评分高，则该孩子的糖果数是左边孩子的糖果数+1，否则为1；
  2. 右规则：若孩子比其右边孩子的评分高，则该孩子的糖果数是右边孩子的糖果数+1，否则为1。
• 先从左往右遍历，使所有孩子的糖果数满足左规则，再从右往左遍历，使所有孩子的糖果数同时满足左右规则，并统计糖果总数即可。

3. 代码

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int right = 1;
        int res = Math.max(right, left[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 1;
            }
            res += Math.max(right, left[i]);
        }
        return res;
    }
}