Description Link to heading
Solution Link to heading
The key point of this problem is that we need traverse two times, one from front to back, the other from back to front.
Code Link to heading
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1);
// front to back
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}
// back to front
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] ) {
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
}
}
int result = 0;
for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
return result;
}
};