(LeetCode 每日一题)135. 分发糖果 ( 贪心 )

题目：135. 分发糖果

思路：贪心+两遍循环，时间复杂度0(n)。
在满足所有人都有一个糖果的情况下，进行两遍循环
第一遍循环：从左到右，满足当ratings[i]>ratings[i-1]时，v[i]=v[i-1]+1
第二遍循环：从右到左，满足当ratings[i]>ratings[i+1]时，v[i]=max(v[i+1]+1,v[i])

C++版本：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        // 预处理出所有人都有1个糖果
        vector<int> v(n,1);
        // 第一遍循环：从左到右，满足当ratings[i]>ratings[i-1]时，v[i]=v[i-1]+1
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1]){
                v[i]=v[i-1]+1;
            }
        }
        // 第二遍循环：从右到左，满足当ratings[i]>ratings[i+1]时，v[i]=max(v[i+1]+1,v[i])
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                v[i]=max(v[i+1]+1,v[i]);
            }
        }
        int sum=0;
        for(auto x:v){
            sum+=x;
        }
        return sum;
    }
};

JAVA版本：

class Solution {
    public int candy(int[] ratings) {
        int n=ratings.length;
        int[] v=new int[n];
        Arrays.fill(v,1);
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1]){
                v[i]=v[i-1]+1;
            }
        }
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                v[i]=Math.max(v[i+1]+1,v[i]);
            }
        }
        int sum=0;
        for(var x:v){
            sum+=x;
        }
        return sum;
    }
}

Go版本：

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