Python one pass 72ms, O(n) time, O(1) space, beats 100%


  • 0
    B
    class Solution(object):
        def candy(self, ratings):
            """
            :type ratings: List[int]
            :rtype: int
            """
            cands = 1
            cands_at_last_peak = 1
            debt = 0
            for i in xrange(1, len(ratings)):
                if ratings[i] < ratings[i-1]:
                    debt += 1
                    continue
                if debt > 0:
                    cands += max((debt+2)*(debt+1)/2-cands_at_last_peak, (debt+1)*debt/2)
                    debt = 0
                    cands_at_last_peak = 1
                cands_at_last_peak = 1 if ratings[i] == ratings[i-1] else cands_at_last_peak + 1
                cands += cands_at_last_peak
            if debt > 0:
                cands += max((debt+2)*(debt+1)/2-cands_at_last_peak, (debt+1)*debt/2)
            return cands

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.