Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 135: Candy (O(n) 2 vectors)
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int candy(vector<int>& ratings) {
vector<int> left(ratings.size(), 1);
vector<int> right(ratings.size(), 1);
for (int i=1; i<left.size(); ++i) {
if (ratings[i]>ratings[i-1]) left[i] = left[i-1] + 1;
else left[i] = 1;
}
for (int i=right.size()-2; i>=0; --i) {
if (ratings[i]>ratings[i+1]) right[i] = right[i+1] + 1;
else right[i] = 1;
}
int sum = 0;
for (int i=0; i<left.size(); ++i) sum += max(left[i], right[i]);
return sum;
}
int main() {
vector<int> ratings {1,4,3,2,4,6,3}; //{1,0,2};
cout << candy(ratings) << "\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.