Leetcode（135）—— Distribute candy

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\ast 10^4$
• $0$ <= ratings[i] <= $2\ast 10^4$

Answer key

Method 1 ： Greedy Algorithm

Ideas

​​   We can 「 Among the neighboring children , Children with high scores must get more candy 」 This sentence is split into two rules , Deal with... Separately .

• The left rule ： When $\text{ratings}[i-1]<\text{ratings}[i]$ when ,$i$ Student No. 1 will have more candy than $i-1$ There are a lot of sweets for child No .
  • Local optimum ： As long as the score on the right is greater than that on the left , The child on the right has one more candy $candyVec[i]=candyVec[i-1]+1$;
  • The best in the world ： Among the neighboring children , The right child with a high score gets more candy than the left child
• Right rule ： When $\text{ratings}[i]>\text{ratings}[i+1]$ when ,$i$ Student No. 1 will have more candy than $i+1$ There are a lot of sweets for child No .
  • Local optimum ： take $candyVec[i+1]+1$ and $candyVec[i]$ The largest amount of candy , Guarantee No. $i$ The number of sweets for a child is greater than that on the left and also greater than that on the right ;
  • The best in the world ： Among the neighboring children , Children with high scores get more candy .

​​   We iterate over the array twice , When each student meets the left rule or the right rule , The minimum number of sweets to be shared . The number of sweets each person eventually gets is the maximum of the two numbers .

​​   In particular , Take the left rule for example ： We iterate through the array from left to right , Assume that the current traversal reaches the position $i$, If there is $\text{ratings}[i-1]<\text{ratings}[i]$ that $i$ Student No. 1 will have more candy than i - 1i−1 There are a lot of sweets for child No , We make $\text{left}[i]=\text{left}[i-1]+1$ that will do , Or we will order $\text{left}[i]=1$.

​​   In real code , Let's calculate the left rule first $\text{left}$ Array , When calculating the right rule, you only need to record the right rule of the current position with a single variable , Calculate the answer at the same time .

Why to take the maximum value is the right thinking ：

We take any two points in the sequence ,A B

• If A > B , Then it is processed according to the left rule ,B No comparison A many ; After processing according to the right rule ,A Certain ratio B many , that A It will be updated （ Bigger ）, but L、R The rules still hold ：B No comparison A many ,A Certain ratio B many ;
• Similarly, we can discuss A<B;
• When A == B,A、B The value of is updated anyway , It doesn't affect L、R The rules

Sum up , The maximum value does not affect the establishment of a rule .

Code implementation

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

Complexity analysis

Time complexity ：$O(n)$, among $n$ It's the number of children . We need to traverse the array twice to calculate the minimum number of sweets that satisfy the left rule or the right rule, respectively .
Spatial complexity ：$O(n)$, among $n$ It's the number of children . We need to save the number of sweets corresponding to all the left rules .

Method 2 ： Constant space complexity

Ideas

​​   be aware Candy is always given as little as possible , And from $1$ Start to accumulate , Each time, you can give one more than the neighboring students , Or reset it to $1$. According to this rule , We can draw the following figure ：

​​   The height of the histogram with the same color is always just $1,2,3\dots$.
​​   And the height is not necessarily in ascending order , It could be $\dots 3,2,1$ In descending order of ：

​​   Notice in the figure above , For the third student , It can be considered as green Ascending part , It can also be considered blue Descending part . because He also scored higher than the students on both sides . Let's modify the sequence a little , Here is the new sequence ​​—— We noticed that The descending part on the right becomes longer （ from 3 Change into 4）, The third student had to be assigned $4$ A candy .

According to the law summarized above , We can propose a solution to this problem ： We enumerate each student from left to right , Remember that the number of sweets given to the former student is $\text{pre}$：

• If the current student scores higher than the previous student , It means that we are in the latest increasing sequence , Directly assigned to the student $\text{pre}+1$ Just a candy .
• Otherwise we are in a decreasing sequence , We directly assign a candy to the current student , And all the students in the decreasing sequence of the student are assigned another candy , To ensure that the quantity of candy still meets the conditions .
  • We don't need to explicitly allocate extra candy , Just record the current decreasing sequence length , Then you can know the amount of candy that needs to be distributed .
  • At the same time, pay attention to when When the current decreasing sequence is the same length as the previous increasing sequence , You need to merge the last student of the nearest increasing sequence into the decreasing sequence .

​​   such , We just record the length of the current decreasing sequence $\text{dec}$, The length of the most recent increment sequence $\text{inc}$ The number of sweets shared with the previous student $\text{pre}$ that will do .

Code implementation

class Solution {
    
public:
    int candy(vector<int>& ratings) {
    
        int n = ratings.size();
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
    
            if (ratings[i] >= ratings[i - 1]) {
    
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ret += pre;
                inc = pre;
            } else {
    
                dec++;
                if (dec == inc) {
    
                    dec++;
                }
                ret += dec;
                pre = 1;
            }
        }
        return ret;
    }
};

Complexity analysis

Time complexity ：$O(n)$, among $n$ It's the number of children . We need to traverse the array twice to calculate the minimum number of sweets that satisfy the left rule or the right rule, respectively .
Spatial complexity ：$O(1)$, We just need a constant space to hold a few variables .