leetcode--16. single-number II

题目：
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
有N个孩子站在一排。为每个孩子分配一个评等值。
你给这些孩子提供糖果，这些孩子必须有以下条件：
每个孩子必须至少有一个糖果。评分高的孩子比邻居得到更多的糖果。
你必须给多少最低限度的糖果？

思路：

• 思路一：
  若用动态规划：

1. 根据限制我们可以想到一个二维数组，从初次扫描开始，每次扫描将评估值与同行前一个结点和前一行后一个结点的值比较，如果大于就加一。
2. 何时结束：N个值，最多进行N次循环，因为最多N个不同的数，最大糖果差为N。
   本题，使用N * N的数组会超出内存限制，于是改用2 * N的数组，其实，也只用到两行，前一行，后一行。

• 思路二：
  第一遍从左向右扫描保证比左边邻居大1
  第二遍从右向左扫描保证比右边邻居大1

import java.util.*;
public class Solution {
    public int candy(int[] ratings) {
        if(ratings.length == 0)
            return 0;
        if(ratings.length == 1)
            return 1;
        int[] candy = new int[ratings.length];
        Arrays.fill(candy, 1);
        int sum = 0;
        for(int i = 0; i < ratings.length - 1; i++)
            if(ratings[i] < ratings[i + 1])
                candy[i + 1] = candy[i] + 1;
        for(int i = ratings.length - 1; i > 0; i--){
            sum += candy[i];
            if(ratings[i] < ratings[i - 1] && candy[i] >= candy[i-1])
                candy[i-1] = candy[i] + 1;
        } 
        sum += candy[0];
        return sum;
    }
}