Java. 1ms. Simple Solution with detailed explaination
Intuition\n Describe your first thoughts on how to solve this problem. \nBasic Trapping Rainwater like solution. https://leetcode.com/problems/trapping-rain-wat
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBasic Trapping Rainwater like solution. https://leetcode.com/problems/trapping-rain-water/\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nObservations : \n- init with all 1.\n- we only give one more when we see adjacent increase (both from left to right).\n- I want to use some case to illustrate this.\n- notice we don\'t care for the exact values of ratings, only their relation\n\nthe rating is similar to \'wave\', increase of decrease\n\nlet\'s look at this case:\n```\nratings: [1,3,6,9,4,2]\ncandies: [1,2,3,4,2,1]\n```\n\nthe highest rating is 9, when scan from left to right, num of candies should be 4, scan right to left, it should be 3, then we choose the larger value.\n\nand let\'s look at some case containing adjacent-equal\n\nwhen there are adjacent-equal, lets look at some cases:\n\n```\nratings: [1,2,3,3,3,3,4,5]\ncandies: [1,2,3,1,1,1,2,3]\n```\n\n```\nratings: [1,2,8,8,8,8,8,2]\ncandies: [1,2,3,1,1,1,2,1]\n```\n\nwith these cases it should be easier to understand\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\n    public int candy(int[] ratings) {\n        int[] cendies = new int[ratings.length];\n        \n        for(int i=0; i<cendies.length; ++i){\n            cendies[i]=1;\n        }\n\n        for(int i=1; i<cendies.length; ++i){\n            if(ratings[i]>ratings[i-1]){\n                cendies[i]=cendies[i-1]+1;\n            }\n        }\n\n        for(int i=cendies.length-2; i>=0; --i){\n            if(ratings[i]>ratings[i+1] && cendies[i]<cendies[i+1]+1){\n                cendies[i]=cendies[i+1]+1;\n            }\n        }\n\n        int sum=0;\n        for(int i=0; i<cendies.length; ++i){\n            sum+=cendies[i];\n        }\n        return sum;\n    }\n}\n```
['Array', 'Greedy', 'Java']