原題

一直線上站了N個孩子，每個孩子都有一個屬於自己的數字，現在按照如下規則給孩子分發糖果：每個孩子至少有一個糖果；相鄰的孩子中數字比較大的那個拿的糖果也比較多。求最少要發掉多少個糖果。

注意點：

例子:

輸入: ratings = [1, 2, 3, 2]

輸出: 7

解題思路

從前往後遍歷的時候，我們只考慮升序的序列，對於其中一段升序的序列，最理想的情況是按照1,2,3…這樣分發糖果；而對於降序的序列，如果從後往前遍歷就也變成升序的了。通過前序和後序遍歷後，升序與降序的交接處那個點會有兩個值，因為要比兩邊的孩子拿到的糖果都多，所以取較大的那個值。這時候得到的數組就是在滿足題目要求前提下每個孩子拿到的最少的糖果數，返回它的和即可。

AC源碼

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        n = len(ratings)
        candy = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candy[i] = candy[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candy[i] = max(candy[i], candy[i + 1] + 1)
        return sum(candy)


if __name__ == "__main__":
    assert Solution().candy([1, 2, 3, 7, 4, 3, 2, 1]) == 21

歡迎查看我的Python">Github (https://github.com/gavinfish/LeetCode-Python) 來獲得相關源碼。