135. Candy

Hint

class Solution {
public:
    int candy(vector<int>& ratings)
    {
        // Initialize a vector to store the number of candies for each child, with each child initially getting 1 candy

        // First pass: Traverse from left to right
        for ()
        {
            // If the current child's rating is higher than the previous child's rating
                // Give the current child one more candy than the previous child
            }
        }

        // Second pass: Traverse from right to left
        for ()
        {
            // If the current child's rating is higher than the next child's rating
                // Ensure the current child has more candies than the next child,
                // taking the maximum between the current count and one more than the next child's count
            }
        }
        // Sum up all the candies to get the total number of candies needed
    }
};

Solution

class Solution {
public:
    int candy(vector<int>& ratings)
    {
        int n = ratings.size();
        vector<int> candy(n, 1);

        for (int i = 1; i < n; ++i)
        {
            if (ratings[i] > ratings[i - 1])
            {
                candy[i] = candy[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; --i)
        {
            if (ratings[i] > ratings[i + 1])
            {
                candy[i] = max(candy[i], candy[i + 1] + 1);
            }
        }
        return accumulate(candy.begin(), candy.end(), 0);
    }
};

• T:
  $O(n)$
• S:
  $O(n)$