C++  |  O(n) time, O(1) space  |  Intuitive Explanation
Intuition\nWhen there\'s a group of n ascending ratings, we can just assign 1,2,...,n candies. For example, if ratings=[3,6,7,10], then we can assign candies [1
**Intuition**\nWhen there\'s a group of `n` ascending ratings, we can just assign `1,2,...,n` candies. For example, if `ratings=[3,6,7,10]`, then we can assign candies `[1,2,3,4]` to minimize the number of candies given. Similarly, for `n` descending ratings, we can assign `n,n-1,...,1` candies.\n\nThe only tricky case is when a rating is a "peak". In the case `ratings=[1,3,5,4]`, the `5` acts as a peak. Since there\'s a group of `3` ascending candies before the peak (including the peak itself), we should assign the peak `3` candies, but there\'s a group of `2` descending candies after the peak (including the peak itself). If this happens, we should assign the peak `max(3,2) = 3` candies to satisfy all conditions.\n\nIn the case there\'s a group with all the same ratings, we can just assign them `1` candy, given that they aren\'t part of a peak or valley.\n\n```c++\nclass Solution {\npublic:\n    int direction(int x, int y) {\n        if (x == y) return 0;\n        return (x > y ? -1 : 1);\n    }\n    \n    int candy(vector<int>& ratings) {\n        int n = ratings.size();\n        int i = 0, prev = 1;\n        int ans = 1;\n        while (i + 1 < n) {\n            int run = 1, dir = direction(ratings[i], ratings[i + 1]);\n            while (i + 1 < n && dir == direction(ratings[i], ratings[i + 1])) {\n                run++;\n                i++;\n            }\n            if (dir == 0) {\n                ans += run;\n                ans -= 1;\n                prev = 1;\n            } else {\n                ans += run * (run + 1) / 2;\n                if (dir == -1) {\n                    ans -= min(prev, run);\n                } else {\n                    ans -= 1;\n                }\n                prev = run;\n            }\n        }\n        return ans;\n    }\n};\n```\n\n**Time Complexity:** O(n) - One pass through the array.\n**Space Complexity:** O(1) - Only constant number of extra variables used.\n\n\n**Upvote** if you like quick and simple explanations!\n\n**Join our discord** to meet other people prepping for interviews!\n**https://discord.gg/7wpQQFYC**
['Greedy', 'C', 'C++']