Leetcode 135.分发糖果

Posted on |

方法

方法1：左右扫描

  • 从左向右移动：If ratings[i] > ratings[i-1], then candy[i] = candy[i-1]+1.
  • 从右向左移动：If ratings[i] > ratings[i+1], then candy[i] = max(candy[i], candy[i+1]+1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        N=len(ratings)
        candy=[1]*N

        # left scan
        for i in range(1,N):
            if ratings[i]>ratings[i-1]:
                candy[i]=candy[i-1]+1

        # right sacn
        for i in range(N-2,-1,-1):
            if ratings[i]>ratings[i+1]:
                candy[i]=max(candy[i],candy[i+1]+1)
        print(candy)
        return sum(candy)

方法2：左右扫描 & 贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        candy=[1]*len(ratings)
        self.greedy(ratings,candy)

        ratings.reverse()
        candy.reverse()
        self.greedy(ratings,candy)
        return sum(candy)

    def greedy(self,ratings,candy):
        for i in range(1,len(ratings)):
            if ratings[i]>ratings[i-1]:
                candy[i]=max(candy[i],candy[i-1]+1)

参考资料