牛客网：分糖果问题

 这题麻，题干中给出了最少，其实很明显要用贪心了。

那么我们如何来贪心呢，众所周知，最少其实就是1，我们很自然想到，和他相邻的，如果比他大，那就最少加一即可保证最小，有了这个概念，我们可以来谈谈这题的思路。

我们首先从左往右看，假定所有都只要1，如果当前数比前一个数要大，那么我们就直接用前面的最小糖果数加一，否则不处理。

这样一遍后很明显，我们无法保证如果当前数比后面大，但是糖果数也比后面大这么一件事，因为我们第一遍是只看了当前数和前面数的比较。

为了修正，我们需要从右往左再看一遍，如果当前数比右边大，而且糖果数是小于等于右边的(取等于是因为第一次遍历的时候我们并没有处理等于号）

代码如下所示：

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int n=arr.size();
        vector<int> num(n, 1);
        for(int i=1;i<n;++i){
            if(arr[i]>arr[i-1]){
                num[i]=num[i-1]+1;
            }
        }
        int res=num[n-1];
        for(int i=n-2;i>=0;i--){
            if(arr[i]>arr[i+1] && num[i]<num[i+1]){
                num[i]=num[i+1]+1;
            }
            res+=num[i];
        }
        return res;
    }
};