135. 分发糖果

算法记录

LeetCode 题目:

  老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。


思路


说明

一、题目

  你需要按照以下要求,帮助老师给这些孩子分发糖果:
    每个孩子至少分配到 1 个糖果。
    评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
  那么这样下来,老师至少需要准备多少颗糖果呢?

二、分析

  • 需要判断是左右两边的评分大小来进行糖果的分发.
  • 可以先朝一个方向上看, 大于前一个则糖果 +1, 再向另一个方向看.
  • 需要注意第二次看的时候不能简单的将之前的糖果取出来 +1, 因为有可能重复发糖果, 只要取其中较大的数量即可.
class Solution {
    public int candy(int[] ratings) {
        int[] candy = new int[ratings.length];
        candy[0] = 1;
        for(int i = 1, j = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i - 1]) j++;
            else j = 1;
            candy[i] = j;
        }
        for(int i = ratings.length - 2, j = 1; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) j++;
            else j = 1;
            candy[i] = Math.max(candy[i], j);
        }
        int num = 0;
        for(int i = 0; i < candy.length; i++) num += candy[i];
        return num;
    }
}

总结

脑筋急转弯。

上一篇:asp dotnet core 提示 Cannot access a disposed object 解决方法


下一篇:SAS - Retain Statement