LeetCode Candy


LeetCode解題のCandy
原題
直線的にN人の子供が立っていて、すべての子供は自分の数字を持っていて、今以下の規則に従って子供にキャンディを配布します:すべての子供は少なくとも1つのキャンディがあります;隣の子の中で数字が大きい方が持っているキャンディも多いです.最低何個のキャンディを出すことを求めます.
注意点:
  • なし
    例:
    入力:ratings=[1,2,3,2]
    出力:7
    問題を解く構想.
    行った後に遍歴する時、私達は昇順の序列だけを考慮して、その中の1段の昇順の序列に対して、最も理想的な情況は1,2,3...このようにキャンディを配布します;降順のシーケンスについては,後から先へ遍歴すれば昇順になる.前序と後序を遍歴すると、昇順と降順の受け渡し先の点に2つの値があり、両側の子供が手に入れたキャンディよりも多いので、その値を大きくします.このとき得られる配列は,テーマの要件を満たす前提で,子ども一人当たりの最低のキャンディ数を返し,その和を返すことでよい.
    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

    私のGithub(https://github.com/gavinfish/LeetCode-Python)を使用して、関連するソースコードを取得します.