(LeetCode 面试经典 150 题) 135. 分发糖果 （贪心）

题目：135. 分发糖果

思路：贪心，时间复杂度0(n)。
先给所有人一颗糖果，然后从左到右遍历，ratings[i]>ratings[i-1]时，分配的糖果比前一个多一个：v[i]=v[i-1]+1。
在从右到左遍历，当ratings[i]>ratings[i+1]时，维护v[i]分配的糖果比后一个v[i+1]多1个,：v[i]=max(v[i],v[i+1]+1)。

C++版本：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        vector<int> v(n,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]=max(v[i],v[i+1]+1);
            }
        }
        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],v[i+1]+1);
            }
        }
        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:=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:=n
    for _,x:=range v {
        sum+=x
    }
    return sum
}