Niuke.com: Candy distribution

  This question is numb , At least... Is given in the stem , In fact, it is obvious to use greed .

So how can we be greedy , as everyone knows , At least it is 1, We naturally think of , Next to him , If you're older than him , Then add at least one to ensure the minimum , With this concept , We can talk about the idea of this problem .

Let's first look from left to right , Assume that everything is as long as 1, If the current number is larger than the previous number , So we just add one to the minimum number of candies , Otherwise, it will not be dealt with .

It's obvious that , We cannot guarantee that if the current number is larger than the following , But the number of sweets is also bigger than that of the later , Because we only looked at the comparison between the current number and the previous number for the first time .

To fix , We need to look again from right to left , If the current number is larger than the right , And the number of sweets is less than or equal to that on the right ( The reason for taking equals is that we didn't deal with the equals sign in the first traversal ）

The code is as follows ：

class Solution {
public:
    /**
     * pick candy
     * @param arr int integer vector the array
     * @return int integer 
     */
    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;
    }
};