🌕 🌗 135. 分发糖果

难度: 🌕 🌗

问题描述

---

解法

class Solution {
    public int candy(int[] ratings) {
        // 思路：
        // 2 次贪心 - 一次 只和左边的孩子比较大小；一次只和右边的孩子比较大小，取较大值，最后求和
        int len = ratings.length;
        int[] array = new int[len];
        Arrays.fill(array, 1); // 先保证每个孩子手中至少一个糖果
        // 只和 左边孩子比较，判断 cur 是否需要增加糖果数
        for(int i = 1; i < len; i ++) {
            if(ratings[i] > ratings[i - 1]) {
                array[i] = array[i - 1] + 1; // 保证比左边孩子糖果数多
            }
        }
        // 只和 右边孩子比较
        for(int i = len - 2; i >= 0; i --) {
            if(ratings[i] > ratings[i + 1]) {
                array[i] = Math.max(array[i], array[i + 1] + 1);
            }
        }
        // 遍历求糖果总数
        int res = 0;
        for(int i : array) {
            res += i;
        }
        return res;
    }
}

---

输出