# one pass constant space C++ solution.

• The idea is straightforward: if you draw a graph based on ratings, to satisfy minimum total number, the increasing line should always start with 1 candy; the decreasing line should always end with 1 candy. We can achieve that by following those rules:

• In increasing line, i simply gets 1 more candy than i - 1;

• In decreasing line, i simply gets 1 less candy than i -1. However, at the end of this decreasing trend, # of candy could be greater or smaller than 1; if this happens we just need to 'normalize' the # of candy from 'start of trend + 1' to end of trend.

• If rating of i is the same as i - 1, it depends on previous trend.

Code is a bit ugly but logic should be clear. Also run time seems to vary, got 29 ms first submission, then 43 and 36.

class Solution {
public:
int candy(vector<int>& ratings) {
if (ratings.empty())
return 0;
int ret(1);
bool increase(true);
int start(0)/*The begining of increasing/decreasing trend*/, lastCandy(1), lastRating(ratings[0]);
for (int i = 1; i < ratings.size(); ++ i) {
if (ratings[i] > lastRating) {
if (increase) { // continue increasing
ret += ++ lastCandy;
} else {//start increasing
if (lastCandy > 1) { // decrease # candies from start + 1 to i - 1
ret -= (i - 1 - start) * (lastCandy - 1);
} else { // increase # candies from start to i - 1
ret += (i - start) * (1 - lastCandy);
}
lastCandy = 2; // i - 1 has 1 candy, i has 2
ret += 2;
start = i - 1;
}
lastRating = ratings[i];
increase = true;
} else if (ratings[i] < lastRating) {
if (increase) { // start decreasing
start = i - 1;
} else
;
ret += -- lastCandy;
increase = false;
lastRating = ratings[i];
} else if (ratings[i] == lastRating) {
if (increase) {
;
} else {
if (lastCandy > 1) { // decrease # candies from start + 1 to i - 1
ret -= (i - 1 - start) * (lastCandy - 1);
} else { // increase # candies from start to i - 1
ret += (i - start) * (1 - lastCandy);
}
start = i;
}
ret ++;
lastCandy = 1;
}
}
if (!increase) { // normalize from start/(start + 1) to ratings[ratings.size() - 1]
int i = ratings.size() - 1;
if (lastCandy > 1) {
ret -= (i - start) * (lastCandy - 1);
} else {
ret += (i - start + 1) * (1 - lastCandy);
}
}

return ret;
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.