0135.cpp (1492B)
1 // original solution - accepted 2 class Solution { 3 public: 4 int candy(vector<int> &ratings) { 5 // place holder rating for easy neighbor calculation 6 ratings.insert(ratings.begin(), -1), ratings.push_back(-1); 7 int n = ratings.size(); 8 9 // sort by rating remembering the original index 10 vector<pair<int, int>> vec; 11 vec.reserve(n); 12 for (int i = 1; i < n - 1; i++) 13 vec.push_back({ratings[i], i}); 14 sort(vec.begin(), vec.end()); 15 16 vector<int> res(n, 1); // 'Each child must have at least one candy' 17 res.front() = res.back() = 0; // except placeholders 18 for (auto &[rating, index] : vec) { 19 if (rating < ratings[index + 1]) res[index + 1] = max(res[index + 1], res[index] + 1); 20 21 if (rating < ratings[index - 1]) res[index - 1] = max(res[index - 1], res[index] + 1); 22 } 23 24 return accumulate(res.begin(), res.end(), 0); 25 } 26 }; 27 28 // improved solution - same logic no nonsense 29 class Solution { 30 public: 31 int candy(vector<int> &ratings) { 32 int n = ratings.size(); 33 if (n <= 1) return n; 34 35 vector<int> res(n, 1); 36 for (int i = 0; i < n - 1; i++) { 37 if (ratings[i] < ratings[i + 1]) res[i + 1] = res[i] + 1; 38 } 39 40 for (int i = n - 1; i > 0; i--) { 41 if (ratings[i] < ratings[i - 1]) res[i - 1] = max(res[i - 1], res[i] + 1); 42 } 43 44 return accumulate(res.begin(), res.end(), 0); 45 } 46 };