LeetCode 135. Candy

每日題。依照小朋友的分數來發糖果，同樣分數拿到不同數量的糖果沒關係，但是比低分的人一定不行拿更多，其實也不是很公平。

題目

有n個小孩排隊，陣列ratings代表個每個小孩的分數。
你要發糖果給這些小孩，並滿足以下要求：

• 每個小孩至少拿到一顆糖
• 如果某小孩比相鄰的小孩分數更高，則必須分到更多的糖

求最少需要幾顆糖。

解法

其實一開始想到這解法並沒有嚴謹的證明，反而是AC之後才想清楚為什麼可行。

每人至少要有一顆，那就每人發一顆，之後慢慢調整。初始化長度N的陣列a，裡面全都是1。
從左往右遍歷，如果當前小孩i的分數高於左方i-1，而糖果數又沒比較多，則補發到比上一個多1顆。
再改成從右往左遍歷回去，如果當前小孩i分數高於右方i+1，且糖果數不夠高，一樣改成比右方多一顆。
最後把每個人糖果加總就是答案。

重點在於如何證明這個方法是對的？試想以下例子：

ratings = [4,3,1,2]
初始 a = [1,1,1,1]
左往右 [1,1,1,2]
右往左 [3,2,1,2]

可以看出向右處理時，會使得a成為多個單調上升的序列，保證每個小孩一定比左方小孩拿得更多。
那從右往左掃回去，更改糖果數量為何不會破壞先前確定好的順序？
當我們把a[i]設為a[i+1]時，有兩種情況：

1. ratings[i-1]<=ratings[i]，所以a[i]增加不會影響兩者關係
2. ratings[i-1]>ratings[i]，有可能使a[i-1]小於a[i]，但是會在下一步驟中被修正

基於以上兩點，可以保證此方法的正確性。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        N=len(ratings)
        a=[1]*N
        
        for i in range(1,N):
            if ratings[i-1]<ratings[i] and a[i-1]>=a[i]:
                a[i]=a[i-1]+1
        
        for i in range(N-2,-1,-1):
            if ratings[i+1]<ratings[i] and a[i+1]>=a[i]:
                a[i]=a[i+1]+1
        
        return sum(a)