leetcode: 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?

原问题链接：https://leetcode.com/problems/candy/

 

问题分析

　　这个问题比较困难，难在怎么找到满足最小值的条件。给定一个数组来说，它里面的元素值的分布不一定是规则的，所以可能如下面的图形所示： 

 

　　而这个时候，如果我们需要去求它的最小分布值，可以这么来考虑。对于所有的元素来说，它对应的初始值都是1。对于每个元素来说，我们需要去比较它和它周边的值，如果它周边的值比它大。那么那个比它大的值就在它对应值的基础上加一。对于我们循环遍历来说，一般是从一头到另一头，那么这个时候比较好判断比如说从左到右递增的序列，对于碰到的后面比前面大的元素，都在前面的基础上加一。可是对于从前往后来说递减的元素，这里就不能处理了。

　　这时候，我们从前往后的过程正好实现了对递增的序列累加。而对于递减的序列来说，从相反的方向来看，它其实也可以说是递增的。那么只要有元素值的增减，它们也应该满足前面的需求。我们也可以从后往前，针对这种情况进行调整。只不过这个时候，我们要选择的值是当前值candies[i] 和candies[i + 1] + 1中最大的那个。

　　这样，我们在最后再把整个数组里元素相加，就得到最后的结果了。详细的代码实现如下：

 

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