Candy

题目：
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?

Solution:

public class Solution {
public int candy(int[] ratings) {
int sum = 0;//记录总糖数
int N = ratings.length;
int[] lc = new int[N];//从左往右
int[] rc = new int[N];//从右往左
if(N == 0) {
return sum;
}
lc[0] = 1;
for(int i = 1; i < N; i++) {
if(ratings[i] > ratings[i - 1]) {
lc[i] = lc[i - 1] + 1;
} else {
lc[i] = 1;
}
}
rc[N - 1] = 1;
for(int i = N - 2; i >= 0; i--) {
if(ratings[i] > ratings[i + 1]) {
rc[i] = rc[i + 1] + 1;
} else {
rc[i] = 1;
}
}
for(int j = 0; j < N; j ++) {
sum += Math.max(lc[j], rc[j]);
}
return sum;
}
}

思路：
lc和rc两个数组分别用来记录从左向右扫描和从右向左扫描时，每个孩子至少需要给的糖果数。然后取两者之间的最大值。

微信图片_20180310185723.jpg