LeetCode 135. 分发糖果

1、题目

分发糖果 - 力扣（LeetCode） https://leetcode-cn.com/problems/candy/submissions/

2、题解

本来我看到这个题目是困难，心想，凉凉。尼玛，又要不知道挖多久了。结果看了题目之后，我一度怀疑这个题目的难度定错了，这题很简单。
题意是说老师分糖，最少一块，相邻比较，分高者多
解决方法就是首先拿一个数组来记录每个位置的发糖数量，初始为每人一块。
然后进行两次遍历，先进行从前向后的遍历，如果后面的分数比前面大，就在前面得到的糖果的基础上加1；再进行从后向前的遍历，如果前面的分数大于后面且前面分到的糖果少于后面，就在后面得到的糖果的基础上加1；
最后，对糖果数组进行累加即可。

3、代码

//两次遍历大法
    class Solution {
        public int candy(int[] ratings) {
            int length = ratings.length;
            int[] saveValueAry = new int[length];
            //填充值
            for (int i = 0; i < length; i++) {
                saveValueAry[i]=1;
            }
            //从前到后
            for (int i = 1; i < length; i++) {
                if(ratings[i]>ratings[i-1]){
                    saveValueAry[i]=1+saveValueAry[i-1];
                }

            }
            //从后到前
            for (int i = length-2; i>=0; i--) {
                if(ratings[i]>ratings[i+1]&&saveValueAry[i]<=saveValueAry[i+1]){
                    saveValueAry[i]=saveValueAry[i+1]+1;
                }
            }
            //累加
            int Sum=0;
            for (int i = 0; i < length; i++) {
                Sum+=saveValueAry[i];
            }

            return Sum;
        }
    }

4、执行结果

image.png