Simple O(n) Python Solution faster than 99% with explanation
In Short :\nSplit ratings array to multi strictly decreasing sub ratings, and update candy with each sub ratings(suppose to be like n, n-1, ......, 2, 1) base o
**In Short :**\nSplit ratings array to multi **strictly decreasing** sub ratings, and update candy with each sub ratings(suppose to be like n, n-1, ......, 2, 1) base on length and the last candy from last sub ratings .\n\n**Detail :**\nWe have three cases :  current rating  (\'>\'  , \'=\'  , \'<\' )  last rating\n\nIf is greater, then we simply take last candy + 1.\nif is equal, then we set candy to 1.\nIf is less, then we set candy to 1, however if the last candy is also 1,  we have to update the last candy to 2, since the last rating is greater.\nWe need to keep updating former candy to make sure higher rating get more candy. After finish all update we can find out the candy we updated is a sequence like n, n-1, ......, 2, 1 or n-1, ......, 2, 1. (depends on whether we update the head of current strictly decreasing sub ratings and n is the number of strictly decreasing sub ratings)\n\ntake ratings : [1,2,4,3,2,1] as example \n\n![image](https://assets.leetcode.com/users/images/f7cae0dd-1835-44d8-8bd1-fd98245f7315_1656912730.3116095.png)\n![image](https://assets.leetcode.com/users/images/eacdb5d5-72b1-4318-afb5-d4dedd68953f_1656912740.543344.png)\n![image](https://assets.leetcode.com/users/images/791024f9-503e-41fc-acb1-9af3e46b41f9_1656912749.0252995.png)\n![image](https://assets.leetcode.com/users/images/ede5c705-b8f8-4014-9403-c8abb76a06e1_1656912758.5754123.png)\n![image](https://assets.leetcode.com/users/images/516a20aa-43c1-43fa-a707-7da05604bde9_1656912765.297426.png)\n\nWe can have some observations from above.( taking sc as the start of current strictly decreasing sub ratings)\n1. Update candy to the sc at most.\n2. Sc\'s candy only update if the length of strictly decreasing sub ratings is  >  Sc\'s candy.\n\nSo we can maintin a stack to keep track on strictly decreasing sub ratings, and update the candy after we get a new strictly decreasing sub ratings. \n(in fact we can calculate total candy for every sub ratings thus we can reduce space complexity to O(1))\n\t\n\tdef candy(self, ratings: List[int]) -> int:\n        #make sure last stack is calculated \n        ratings.append(float(\'inf\'))\n\n        #default set candy to 1\n        candy = [1] * len(ratings)\n\n        #stack init with index 0\n        stack_startindex, stack_leftcandy, stack_count  = 0, 1, 1\n\n        for i in range(1, len(ratings)) :\n\n            #if rating is greater or equal : start new stack and update candy for old stack\n            if ratings[i] >= ratings[i-1] :\n\n                #set candy to n, n-1, ......, 1 in the stack\n                if stack_count > stack_leftcandy :\n                    for j in range(stack_startindex, i) :\n                        candy[j] = stack_count \n                        stack_count -= 1\n\n                #set candy to k(leftcandy), n, n-1, ......, 1 in the stack \n                else :\n                    for j in range(stack_startindex+1, i) :\n                        candy[j] = stack_count-1 \n                        stack_count -= 1\n\n                #set current candy to left + 1 if rating is greater\n                #set current candy to 1 if rating is equal\n                if ratings[i] > ratings[i-1] : candy[i] = candy[i-1] + 1\n                else : candy[i] = 1\n\n                #init new stack start from i\n                stack_startindex, stack_leftcandy, stack_count = i, candy[i], 1\n\n            #if rating is less : update stack count\n            else : stack_count += 1\n\n        #sum all candy except the last one we added first\n        return sum(candy[:-1])\n\n
['Greedy', 'Python', 'Python3']