Idea: envision the sequence of ratings as uphill (increase) and downhill (decrease) segments. Here the valley points (lower than both neighbors, and the index 0 and n-1 can be treated as special case) are the key to solve the problem. We make the following observations:

[1] The valley points should be given only 1 candy for minimum candies

[2] The valley points won't be affected by neighbors

[3] So we start from each valley point, and walk uphills on both sides (could be only one side for index 0 and n-1) and update the minimum candies required for each rating we met.

Thus, T(n) = O(n)

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