Python easy code O(n) two pass


  • 0
    X
    class Solution:
        # @param {integer[]} ratings
        # @return {integer}
        def candy(self, ratings):
            n = len(ratings)
            if n == 0: return 0
            f = [1 for i in xrange(n)]
            for i in xrange(1, n):
                if ratings[i] > ratings[i-1]:
                    f[i] = max(f[i], f[i-1] + 1) 
            f.reverse()
            ratings.reverse()
            for i in xrange(1, n):
                if ratings[i] > ratings[i-1]:
                    f[i] = max(f[i], f[i-1] + 1) 
            ans = 0
            for i in f:
                ans += i
            return ans

Log in to reply
 

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