<p>There are <code>n</code> children standing in a line. Each child is assigned a rating value given in the integer array <code>ratings</code>.</p>

<p>You are giving candies to these children subjected to the following requirements:</p>

<ul>
	<li>Each child must have at least one candy.</li>
	<li>Children with a higher rating get more candies than their neighbors.</li>
</ul>

<p>Return <em>the minimum number of candies you need to have to distribute the candies to the children</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> ratings = [1,0,2]
<strong>Output:</strong> 5
<strong>Explanation:</strong> You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> ratings = [1,2,2]
<strong>Output:</strong> 4
<strong>Explanation:</strong> You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == ratings.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= ratings[i] &lt;= 2 * 10<sup>4</sup></code></li>
</ul>

class Solution{
public:
	int candy(vector<int> &ratings){
		int numChildren = ratings.size();
        vector<int> minCandies(numChildren,0);
        vector<int> minimas;

        //edges
        if(numChildren == 1){
            return 1;
        }
        if(numChildren >= 2 && ratings[1] >= ratings[0]){
            minimas.push_back(0);
            minCandies[0] = 1;
        }
        if(numChildren >= 2 && ratings[numChildren-2] >= ratings[numChildren-1]){
            minimas.push_back(numChildren-1);
            minCandies[numChildren-1] = 1;
        }

        for(int i=1; i<numChildren-1; i++){
            if(ratings[i-1] >= ratings[i] && ratings[i+1] >= ratings[i]){
                minimas.push_back(i);
                minCandies[i] = 1;
            }
        }

        for(auto index : minimas){
            // Go left
            int cur = index;
            while(cur != 0 && ratings[cur-1] > ratings[cur]){
                minCandies[cur-1] = max(minCandies[cur-1], minCandies[cur] + 1);
                cur--;
            }
            
            // Go Right
            cur = index;
            while(cur != numChildren-1 && ratings[cur+1] > ratings[cur]){
                minCandies[cur+1] = max(minCandies[cur+1], minCandies[cur] + 1);
                cur++;
            }
        }

        int sum = 0;
        for(int candy : minCandies){
            sum += candy;
        }
        return sum;
    }
};

20600