# 0135. Candy
###### tags: `Leetcode` `Medium` `Greedy` `Two Pass`
Link: https://leetcode.com/problems/candy/description/
## 思路
第一次从前往后遍历 保证如果```ratings[i]>ratings[i-1]```那么```candy[i]>candy[i-1]```
第二次从后往前遍历 保证如果```ratings[i]>ratings[i+1]```那么```candy[i]>candy[i+1]```
由于```candy[0]=1``` ```candy[n-1]```也是按最小的取
结果一定valid
## Code

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        ans = [1]*n
        for i in range(n):
            if i==0: continue
            if ratings[i]>ratings[i-1]:
                ans[i] = ans[i-1]+1
            elif ratings[i]<ratings[i-1]:
                ans[i] = 1
        for i in range(n-1, -1, -1):
            if i==n-1: continue
            if ratings[i]>ratings[i+1]:
                ans[i] = max(ans[i+1]+1, ans[i])
            elif ratings[i]<ratings[i+1]:
                ans[i] = max(1, ans[i])
        print(ans)
        return sum(ans)

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