[allocation problem] 135 Distribute candy

One 、 subject

n Two kids in a row . Give you an array of integers ratings Indicates the score of each child .

You need to follow these requirements , Distribute candy to these children ：

Each child is assigned at least 1 A candy .
Children with higher scores from two adjacent children will get more candy .
Please distribute candy to each child , Calculate and return what needs to be prepared Minimum number of sweets .

Example 1：

Input ：ratings = [1,0,2]
Output ：5
explain ： You can give the first one separately 、 the second 、 The third child distributed 2、1、2 Candy .
Example 2：

Input ：ratings = [1,2,2]
Output ：4
explain ： You can give the first one separately 、 the second 、 The third child distributed 1、2、1 Candy .
The third child only got 1 Candy , This satisfies two conditions in the problem surface .

Tips ：

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

Two 、 Answer key

Here with 455 equally , There are relatively greedy strategies , But there is no need to sort and select , Because the title here requires comparison with adjacent elements , So we can rely on two iterations to operate .
First , Because every child must have a candy , So we define a candy allocation array with a value of one .
Then traverse for the first time ： Traversing from front to back , If the corresponding score of this position is larger than that of the previous position , Then the candy allocation array value of this position is the candy allocation array value of the previous position plus one . Second traversal ： Go back and forth , If the corresponding score of this position is larger than that of the next position , Then the array value of candy allocation in this position should also be the array value of candy allocation in the next position plus one , However, after the first traversal, the candy allocation value at this position may be greater than that at the previous position . At this time, it meets the requirements of the topic , No operation . So we should compare these two situations , Taking the maximum . Until the traversal is complete .
Last , Sum the values of the candy allocation array , Get the total number of sweets that need to be distributed at least .

3、 ... and 、 Code

class Solution {
    
public:
    int candy(vector<int>& ratings) {
    
      int n=ratings.size();
      vector<int> nums(n,1);
      for(int i=1;i<n;i++){
    
          if(ratings[i]>ratings[i-1]) nums[i]=nums[i-1]+1;
      }
       for(int j=n-1;j>0;j--){
    
          if(ratings[j-1]>ratings[j]&&nums[j-1]<=nums[j]) 
          nums[j-1]=max(nums[j]+1,nums[j-1]);
      }
      return accumulate(nums.begin(),nums.end(),0);
    }
};