Minimize Candy Counts under Adjacent Rating Comparisons
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Distribute candies to children in a line. Every child gets at least one. Whenever one child has a higher rating than an adjacent child, that child must get more candies than that neighbor. Equal ratings impose no relative candy requirement. Return the minimum total number of candies.
```cpp
int candy(vector<int>& ratings);
```
### Examples
```text
Input: ratings = [2,4,3,1]
Output: 7
```
An optimal allocation is `[1,3,2,1]`.
```text
Input: ratings = [3,3,3]
Output: 3
```
### Constraints
- There are between 1 and 50000 children.
- Ratings range from 0 to 50000, inclusive.
Overview: Minimize neighbor-constrained candy allocation with left and right rating-run lower bounds.
