# Python-LeetCode 581 第九招 Greedy algorithm
本單元介紹貪心演算法(Greedy algorithm)，這裡的貪心沒有負面的意思，單純指以當前最有利的方式做決定。貪心演算法通常很直覺，所以寫程式往往簡單，但不是對所有問題都能夠找到最佳解。Greedy通常需要證明，但上機考試與競賽的場合，不需要證明，所以很多人不知道怎麼做的時候就用Greedy寫下去猜猜看，考試本來就是該猜就要猜，不過貪心也要貪的正確。
貪心演算法通常需要搭配排序或優先佇列(priority_queue，常簡稱PQ)，我們在之前的單元已經介紹過優先佇列[Python-LeetCode 581 第五招 優先佇列 Priority Queue/Heap](/QPaqO5-HRF-PLuoBjlKwwA)與排序[Python-LeetCode 581 第八招 Sorting](/MgjnIYXhQvqxJ34wpIcudg)，所以以下會假設讀者已經對這兩種技術有所認識。
## 基本原則
所謂貪心演算法指的是：一個算法由一連串的決定組成，每次決定時都以當時最有利的方式挑選，而且一旦挑選後就不再更改。我們先以舉一個很簡單的例子來說明。
[(題目連結) 455. Assign Cookies (Easy)](https://leetcode.com/problems/assign-cookies/description/)
在這題裡，有若干餅乾要分給一些小孩，每一個小孩有他想要的餅乾大小(願望)，每個小孩最多只能給一塊餅乾，一塊餅乾也只能分給一個小孩，請計算最多可以滿足多少位小孩的願望。
以下是很直覺的思考方式。願望小的小孩比較容易滿足，如果有一個方法可以滿足$k$位小孩，那麼該方法一定可以滿足願望最小的$k$位小孩。
於是我們可以依照小孩願望由小排到大，依序來滿足他們的願望。要滿足某位小孩的願望，若他想要餅乾大小為$x$，我們只要找$\geq x$中最小的餅乾就可以了，因為留下更大的可能可以用來滿足其他人。
所以我們的演算法設計為
1. 將小孩願望排序
2. 將餅乾排序，初始目前檢視餅乾的index $i=0$
3. 把小孩的願望由小到大逐一檢視：
3.1. 逐步增加$i$，找到能滿足願望的第一個(最小)餅乾編號$i$。
3.2. 如果找到，就把餅乾$i$給這位小孩來滿足他。如果找不到，就結束程序。
以下是範例程式，時間複雜度$O(n\log n+m\log m)$，其中$n,m$分別是小孩與餅乾的數量。
```python=
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
ans = 0
i = 0
for child in g:
while i<len(s) and s[i]<child:
i += 1
if i<len(s):
ans += 1
i += 1
else: break
return ans
```
程式寫起來很簡單，這個方法很直覺，但怎麼知道它是對的呢？有些人可能會說：就很直覺啊，路邊隨便找個少林寺掃地的也會這樣做。我們必須證明。如何證明呢？
貪心算法既然是由一連串決策組成，每個決策一旦決定後就不再更改，我們的證明就是要證明每一次當下的決定是對的。通常的證明方式就是：**證明有一個最佳解也做了相同的決定**。
在本題中，我們的決定就是將某個餅乾給了某個小孩。很顯然假如最佳解滿足了$k$個小孩，一定有一個最佳解$OPT$滿足的是願望最小的$k$個小孩。假設$G$是貪心法的解，我們依照小孩的願望由小到大來比對兩組解。假設第一個相異之處發生在小孩$c$，$G$分派餅乾$s$給$c$，但是$OPT$不一樣。
1. 因為$OPT$分派餅乾給最小的$k$個小孩，所以一定有分派餅乾給$c$，根據我們的貪心原則，$G$給的餅乾$s$是當時最小的餅乾，既然$OPT$不一樣，那麼一定是給了$c$一塊更大的餅乾$t>s$。
2. 我們把$OPT$解中的$t\rightarrow c$換成$s\rightarrow c$，換回一塊餅乾$t\geq s$，對它其他的解不會變成更壞，所以最佳解不會變差。
也就是說必然有一個最佳解將$s$分派給$c$，與貪心法一樣。
這個例子中我們看到了貪心法的一些特質。
* 算法由一連串決定組成(由小到大逐一滿足小孩)，每次考慮當前最好決定(挑能夠滿足裡面的最小餅乾)，選擇後就不再更改。
* 算法的正確性必須經過證明，內容就是要證明所下的決定是對的，也就是一定有一個最佳解包含了貪心法所做的決定，而證明的方法通常都是用換的：假設有一個最佳解跟貪心法做的決定不一樣，那麼，我們可以換成一個與貪心法一樣的決定，而解不會變差。
以下我們分幾類來說明貪心法在LeetCode中題目的解法。
## Sweeping：掃地僧一路掃過去
武俠小說中掃地僧的內力往往深不可測，對戰時對他人的攻擊不避不擋，直接一掌掃過去就解決，不必拐彎抹角耍招式。有些貪心算法的題目也是如此，不需要排序也不需要PQ，一路掃過去並貪心的做決策就可以解決。
[(題目連結) 2405. Optimal Partition of String (Medium)](https://leetcode.com/problems/optimal-partition-of-string/)
在這題裡，我們給了一個字串，要把字串切割成每一段都沒有重覆的字元，希望切割數越少越好。
貪心之處在於：早切不如晚切，由前往後掃，碰到有相同字元出現時，不得不切時再切就是最佳解。
如何證明？假設貪心算法與某一最佳解第一段出現不同之處在於：貪心算法切在$x$，而最佳解切在$y<x$。我們將最佳解的這一刀往後移到$x$顯然不會增加切割數，而且後面字串減少前面一截也不會因而變成不合法。
實作程式需要一個紀錄字元出現的紀錄器，我們這裡用set()，以下是範例程式，時間複雜度$O(n)$。
```python=
class Solution:
def partitionString(self, s: str) -> int:
occ = set()
cnt = 0
for c in s:
if c in occ: # repeated char
cnt += 1
occ.clear()
occ.add(c)
# +1 for remaining in occ
return cnt+1
```
[(題目連結) 122. Best Time to Buy and Sell Stock II (Medium)](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)
輸入股票的每日價格，先買後賣，無限次數買賣，但只能買一股，請計算出最大獲利。
把所有上升區段的價差累積起來就是最大獲利，因為連續上升時，累積一次獲利與每天獲利加總後是一樣的，所以只要把每天與前一天是正的價差加起來就好了。
簡單的程式很多寫法，以下範例程式用
zip(price[1:], price)
取出所有對應前後項。當然也可以用很基本的寫法，時間複雜度$O(n)$。
```python=
class Solution:
def maxProfit(self, prices: List[int]) -> int:
d = [max(x-y,0) for x,y in zip(prices[1:],prices)]
return sum(d)
```
[(題目連結) 55. Jump Game (Medium)](https://leetcode.com/problems/jump-game/)
給一個非負整數陣列代表一排格子，陣列的數字代表站在此格時可以向右跳的距離上限，請問從最左邊的格子出發是否可以到達最右邊的格子。
因為跳躍的限制是3的話，你可以跳1,2或3，所以可以到達的格子是一個連續區間。在可以到達的區間內，每一個格子$i$都提供了到達$[i,i+nums[i]]$區間任一位置的可能，取其最大者就是將可到達位置往右延伸。所以我們從起點開始，一直紀錄可到達的上限，在現有上限範圍內，看看是否可以繼續延伸上限，直到可以到達終點或者無法再延伸。
以下是範例程式，時間複雜度$O(n)$。
```python=
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
reach = 0 # max of reachable
i = 0 # current position
while i<=reach and reach<n-1:
reach = max(reach, i+nums[i])
i += 1
return reach>=n-1
```
下面這題與前一題的題目敘述是一樣的，但這題要求的是，最少跳幾次可以到達終點，保證有解。
[(題目連結) 45. Jump Game II (Medium)](https://leetcode.com/problems/jump-game-ii/)
與前一題同樣的，從一個格子往右跳時，可以到達的位置是一個連續區間。對於每一個格子，從起點到達它所需要的最少跳躍次數稱為它的距離的話，那麼距離為$i$的格子構成的是一個連續區間。
下圖是一個例子。距離0只有起點。起點可以到達的三個格子是距離1的格子。從距離1的格子可以到達範圍是距離2，以此類推。
因此，我們只要一步一步往右算過去，維護距離$d$的區間$[left,right]$，每次此範圍內取可以到達的最右端，當作$d+1$的右端，而新左端就是$right+1$。以下是範例程式，時間複雜度$O(n)$。為了方便，程式中維護的是$[left,right)$半區間。
```python=
class Solution:
def jump(self, nums: List[int]) -> int:
step = 0
left,right = 0,1 # reachable [left,right)
while right < len(nums):
t = right
right = max([i+nums[i] for i in range(left,right)])+1
left = t
step += 1
return step
```
[(題目連結) 2366. Minimum Replacements to Sort the Array (Hard)](https://leetcode.com/problems/minimum-replacements-to-sort-the-array/)
給一個正整數數列，每次可以將其中一數分割成兩個總和與原數相等的數字(放在相同的位置)，請問最少經過幾次操作可讓此數列變成**非遞減序列**。
每一次操作就會增加一個元素，所以最後的數列越短，操作次數就越少。一定會有答案，因為最壞就是全部變成1。允許的操作只有分割，分割後數字一定是變小，那麼貪心的策略就是：
**由後往前做，讓後面的數字越大一定越好**。
因為要越大越好，所以
1. 能不分割就不要分割。
2. 一定要分割時，我們可以直接算出要拆幾次才能拆成非遞減，並且讓拆出來的第一個數字越大越好。
3. 假設後面的數字是$last$。前一個數$p>last$，要拆成$\leq last$，我們先算至少要拆成幾個，讓拆出來的數字最小值越大越好的話，就盡可能拆的平均。
以下是範例程式，時間複雜度$O(n)$。
```python=
class Solution:
# greedy, last one as large as possible
def minimumReplacement(self, nums: List[int]) -> int:
ans = 0
last = 10**9 # initial oo
for p in nums[::-1]: #backward
if p<=last: # no split
last = p
continue
q = p//last # split into q or q+1 part
if last*q == p: # divisible
ans += q-1
else:
ans += q
last = p//(q+1)
#
return ans
```
[(題目連結) 765. Couples Holding Hands (Hard)](https://leetcode.com/problems/couples-holding-hands/)
在下面這題裡，有$2n$個人，編號0 ~ $2n-1$，坐在一排椅子上，(0,1)是一對，(2,3)是一對，...。每次可以找兩位交換座位，請問最少要交換幾次才可以讓每一對都坐在彼此相鄰的座位上。
因為最後全部都要相鄰，所以座位編號一定每兩個是坐著一對人。因為交換時並不考慮距離，所以座位只跟編號有關，是否是一排並無關聯。
也許將交換座位想像成交換身上的名牌會更容易些。假設有一組解可將每一對排成相鄰，而且$(p,q)$不是同一對。我們在這組解裡面加上一個$p$與$q$的交換，那麼，很直覺的，最後的結果就是：除了$p$與$q$交換伴侶外，其他的每一對都是相鄰。
我們可以證明一定有一個最佳解中$row[0]$沒有更換座位。假設有一個最佳解$row[0]=p$更換過座位，我們將該解中的其中一次$p$與某$q$交換刪除，那麼最後的結果是$p$與$q$交換了伴侶，其他都成對。我們最後再加上一個他們兩人的伴侶交換，可以得到一樣次數的解。重覆此法，必定存在一個$row[0]$沒變動的解。
因此我們得到一個貪心的解法：由前往後掃，每次保持最前面這位不動，將他的伴侶換到他的旁邊，然後繼續下一對。
以下是範例程式，一開始先記錄所有人所在的座位編號。第9行開始歷遍，每次跳兩格，因為一次處理一對。如果旁邊不是伴侶，就把他換過來。用一個簡單的數學來簡化寫法，像這樣(0,1)是一對，(2,3)是一對的狀況，對於編號$p$，它的伴侶可以表示成$p\oplus 1$，也就是將bit-0取互補，其中$\oplus$是互斥或(exclusive or)。
時間複雜度$O(n)$。
```python=
class Solution:
# greedy works, existing opt with row[0] unchanged
def minSwapsCouples(self, row: List[int]) -> int:
n = len(row)
pos = [0]*n # position of person
for i,x in enumerate(row):
pos[x]=i
cnt=0
for i in range(0,n,2):
j = pos[row[i]^1] # partner of row[i]
if j != i+1: # not in position
cnt += 1 # swap row[i+1]
row[j] = row[i+1]
pos[row[j]] = j # update pos
#end for
return cnt
```
## 單欄位資料排序
下面這題是說每艘船最多載兩個人，且一艘船總重量限制$limit$，給$n$個人的體重，請問至少要幾艘船才能載完。
[(題目連結)881. Boats to Save People (Medium)](https://leetcode.com/problems/boats-to-save-people/)
與前面示範的餅乾分小孩非常類似，只是變成只有一個序列。我們盡可能的能夠一船載兩人。將體重排序後，用兩個指標維護尚未處理的區間$[i,j]$。如果可以共乘，就共乘，否則重的那一個$j$，自己搭一艘船。
以下是範例程式，時間複雜度$O(n\log n)$。結尾若$i=j$的時候，我們不需特別處理，反正就是一艘船。
```python=
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
boat = 0
i,j = 0,len(people)-1
while i <= j:
boat += 1
if people[i]+people[j]<=limit:
i += 1
j -= 1
else:
j -= 1
return boat
```
[(題目連結) 910. Smallest Range II (Medium)](https://leetcode.com/problems/smallest-range-ii/)
給一個陣列以及一整數$k$，每個數字可以選擇$+k$或$-k$，希望最後陣列最大值與最小值的差越小越好。
顯然小的值應該要$+k$，而大的值應該要$-k$，問題是界線在哪裡。我們可以不必動腦筋，先把全部的值都$-k$，再從小到大一路$+2k$，每變動一個就算一下差值，最好(小)的那個就是最佳解。而有時我們不必做到最後，因為當某一個$-k$後的值超過**最小值**$+k$時就不必再試了，因為此後的調整後最小值都不會增加。
以下是範例程式，時間複雜度$O(n\log n)$。
```python=
class Solution:
# all set to -k. Then +2k from small to large
def smallestRangeII(self, nums: List[int], k: int) -> int:
nums = sorted([x-k for x in nums]) # all -k
k += k # 2k
imax = nums[-1]
dif = imax - nums[0]
lim_min = nums[0]+k # cannot smaller than
for e in nums:
if e>=lim_min:
dif = min(dif,imax-lim_min)
break
dif = min(dif,imax-e)
imax = max(imax,e+k)
return dif
```
[(題目連結) 1029. Two City Scheduling (Medium)](https://leetcode.com/problems/two-city-scheduling/)
有$2n$求職者要分配到兩座城市面試，第$i$位到A城市與B城市面試的成本分別是$cost[i][0]$與$cost[i][1]$。要平均分配，就是各有$n$位到城市A與B，求最小的總成本是多少。
假設在最佳解中$i4分配到A而$j$分配到B，則兩者交換必不能降低成本，也就是
$$
cost[i][0]+cost[j][1] \leq cost[i][1]+cost[j][0] \\
cost[i][0]-cost[i][1] \leq cost[j][0]-cost[j][1]
$$
因此答案是把$cost[i][0]-cost[i][1]$最小的$n$個分配到A城市就是最佳解。我們用排序來做就可以了，以下是範例程式，時間複雜度$O(n\log n)$。
```python=
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
n = len(costs)//2
costs.sort(key = lambda x: x[1]-x[0])
t = sum(p[1] for p in costs[:n]) + sum(p[0] for p in costs[n:])
return t
```
## 結構資料排序
在這個類別的題目中，我們需要動用到結構資料的排序，也就是資料可能不只是單一的值。
[(題目連結) 452. Minimum Number of Arrows to Burst Balloons (Medium)](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/)
在XY平面座標上有若干氣球，第$i$個氣球橫跨的X範圍是$points[i][0]$到$points[i][1]$。我們每次選定一個$x$值，垂直發射一枝箭，所有橫跨範圍包含$x$的氣球都會射穿爆炸。請問最少發射幾枝箭可以射破所有的氣球。
每個汽球看成一個區間，要選擇最少的點戳中所有區間。
考慮從左到右發射。考慮右端最小的區間$[s,t]$，我們在此區間至少必須發射一箭，否則此區間無法被射中。又因為$t$是最小右端，假設有一個解最左邊的一箭射在比$t$小的位置，我們可以把這一箭往右移到$t$，不會有任何壞處。也就是必有一最佳解最左一箭射在$t$。
我們可以挑選最小右端射出一箭，並移除此箭射到的任何區間。然後重覆這個步驟。
實際實作這個貪心算法時，我們將所有區間依照右端排序，歷遍所有區間，記錄著前一箭的座標last，保持迴圈不變性：所有左端$\leq last$的區間均已射破。
因此，檢查到下一個區間時，若左端$\leq last$就置之不理，若左端$>last$，就是下一個要射擊的最小右端區間。
以下是範例程式，初始時，last設在一個不可能的小。時間複雜度$O(n\log n)$。
```python=
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: x[1]) # sort by right
last = points[0][0]-1
ans = 0
for le, ri in points:
if le > last:
ans += 1
last = ri
return ans
```
這一題在圖論上其實是interval graph的clique partition (or clique cover)，對於interval graph，他等價於max independent set(找出最多不相交的區間)，在sorting的單元中，我們已經說明過那個版本。
[(題目連結) 135. Candy (Hard)](https://leetcode.com/problems/candy/description/)
有$n$個小朋友排成一排，現在要分糖果給他們，每個小朋友至少要有一塊糖。同時，對於位置相鄰的兩位小朋友A與B，如果A的分數比B分數高的話，A的糖必須比B來得多。如果不相鄰就無此限制。請問最少需要多少糖果才能分配。舉例來說，$ratings = [1,0,2]$，我們的糖果數可以分派為$[2,1,2]$，總共需要5塊糖果。
先講一個比較直覺的做法。從分數由低往高一位一位分配，如果第$i$位左右還沒分派，也就是**相鄰的分數都不低於他**，就分給他一塊糖。如果左右有分數小於他的，就取其最大值加一。
以下是範例程式，第4行加上一個不可能大的分數是當作哨兵，在後面省略邊界檢查，請留意Python在尾端加一個可以同時當左右的哨兵，因為list[-1]是最後一個。第6行開始歷遍排序後的分數與位置，迴圈內就檢查左右鄰居，如果有分數較大者就取最大值，如果沒有就取0。第10行指定這位小朋友的糖果數。
時間複雜度$O(n\log n)$。
```python=
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
ratings.append(100000) #sentinel
num = [0]*n
for v,i in sorted((ratings[i],i) for i in range(n)):
x = num[i-1] if ratings[i-1]<v else 0
if ratings[i+1]<v and num[i+1]>x:
x = num[i+1]
num[i] = x+1
return sum(num)
```
剛才那個$O(n\log n)$複雜度的程式已經可以通過了。打開Runtime排行一看，應該有複雜度更好的解法。
確實，這一題有個時間複雜度$O(n)$的解。
想像我們由左到右分派糖果：
1. 如果分數是下降的，就暫緩分配糖果。
2. 如果碰到上升或相同，表示我們碰到一個山谷，可以將山谷的最低點分派一個糖果，並且沿路回溯，但要注意最後一個山峰必須比較前後取較大者。
以下是範例程式， linear time。
```python=
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
ratings.append(20001)
num = [0]*n
for i in range(1,n+1):
if ratings[i] < ratings[i-1]:
continue # 下降暫緩
j = i-1; k = 1 # 山谷，準備回溯
while j>0 and ratings[j]<ratings[j-1]:
num[j] = k # 往上爬，沿路加一
k += 1
j -= 1
num[j] = k
if j>0 and ratings[j-1]<ratings[j] and num[j-1]>=k:
num[j] = num[j-1]+1 #山峰比較兩邊
#
return sum(num)
```
下面這題是前面射氣球題目的變化，有若干區間，我們要射中每個區間至少兩次。
[(題目連結) 757. Set Intersection Size At Least Two (Hard)](https://leetcode.com/problems/set-intersection-size-at-least-two/)
與每個區間射中一次的思考方式類似，我們將區間依照右端排序，由左往右掃，保持一個list cover是目前已射出座標位置。保持以下迴圈不變性：
1. cover中的點是目前的最佳解，且嚴格遞增。
2. cover中的點都已經盡可能靠右(再往右移動就不是合法的解)
對於下一個進入的區間$[l,r]$，
1. 先以二分搜在cover中到第一個$\geq l$的位置$i$。
2. 若找不到，表示目前的解沒射中此區間，我們要增加兩點$r-1$與$r$。
3. 若cover射中此區間一點(必然是cover[-1])，我們要增加一點，但此處有陷阱，如果cover[-1]==$r$，我們必須增加$r-1$；否則我們增加$r$。
4. 若已經射中兩點以上，就不必做任何事。
我們可以確認迴圈不變性會獲得保持。以下是範例程式，時間複雜度$O(n\log n)$。
```python=
class Solution:
#greedy, sorted by right, add element as large as possible
# for same right check if insert the same tail
def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x:x[1]) # sort by right
cover = []
for l,r in intervals:
i = bisect.bisect_left(cover,l)
if i==len(cover): # cover none
cover += [r-1,r]
elif i==len(cover)-1: # cover one
if cover[-1]==r: # same right
cover[-1:] = [r-1,r] # add r-1
else: # add r
cover.append(r)
#else: pass # cover>1, do nothing
return len(cover)
```
## 以PQ處理動態資料
Priority-Queue(heap)與sorting一樣都常常用在Greedy算法中，如果是靜態資料，通常用sorting比較快速，動態資料就需要用PQ，動態資料是指我們要選取極值的資料是會增加或減少的。
前面有個題目是找點去戳區間，下面這題是找區間來涵蓋給定的點。
[(題目連結) 632. Smallest Range Covering Elements from K Lists (Hard)](https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/)
有$k$個排好序的list，我們要找一個最短的區間包含每個list至少一個元素。最短區間長度有多個時，找最小左端。
首先，所要找的區間左右端必然是在輸入的點之中，否則我們可以縮小區間。但是嘗試所有可能的區間就太差了，本題$k\leq 3500$，每個序列長度$m\leq 50$，最多$n=3500\times 50=175000$個點。
直覺上可以嘗試所有的左端，對於一個固定的左端$left$來說，每一個list應該被放進來的就是$\geq left$的最小元素，對每個list的這個元素取最大就是對應此$left$的最好右端。
如果使用二分搜在每個list找，此法的時間複雜度是$O(nk\log m)$，如果想到沿路二分搜不如一路爬過去，可以省略二分搜，但還是要$O(nk)$。
算法的效率來自避免**不必要的計算**與**重複的計算**。
不必要的計算通常來自性質(數學)，姑且不論。上述算法中有無重複的計算呢？
當$left$移動一步時，重新檢視$k$個list應該納入區間的元素顯然是浪費了，因為大部分的元素都不會變動，只有被移出的那個list(前一步的$left$)，需要重新找。
既然每個list只需要有一個元素參與，我們就將每個list的頭端(最小值)放入一個PQ(min-heap)，每次以PQ的最小值當左端，右端就是PQ的最大值，每次將最小值移出PQ後，將他所來自的list的下一個放入PQ中。
以下是範例程式。為了知道移除的元素來自哪一個list，在PQ中我們放元素的值以及來自哪一個list的tuple。初始時每個list的最小值納入PQ(第6行)，先求一次PQ最大值(第7行)，第10行的curr是紀錄每個list現在跑到第幾個元素。
第11行開始的無窮迴圈會跑到某個list清空時跳出。迴圈內將PQ最小值移出，將他的繼任放入(同list的下一個)，PQ的最大值我們要避免每次重新計算，因為只有一個新進值，只要把新進值與原來最大值比較一下就可以了。替換完畢後檢查一下最佳解，因為左端由小到大，所以只有區間嚴格變小時才替換最佳解。
時間複雜度$O(n\log k)$，因為PQ的大小是$k$。
```python=
class Solution:
# for each possible smallest as left, right is
# max of (min element>=left) from all list
def smallestRange(self, nums: List[List[int]]) -> List[int]:
k = len(nums)
pq = [(nums[i][0],i) for i in range(k)] # (val, from)
imax= max(pq)[0]
heapq.heapify(pq)
best = [pq[0][0], imax] # current solution
curr = [0]*k # head index of each list
while True:
v,i = heapq.heappop(pq) # smallest=v, from i
curr[i] += 1
if curr[i]>=len(nums[i]): break # no next
imax =max(imax,nums[i][curr[i]])
heapq.heappush(pq,(nums[i][curr[i]],i))
if imax-pq[0][0]<best[1]-best[0]:
best = [pq[0][0], imax]
return best
```
下面這題是個job scheduling(排程)問題。
[(題目連結) 630. Course Schedule III (Hard)](https://leetcode.com/problems/course-schedule-iii/)
每個工作有需要的耗費時間與deadline，但沒有到達時間，也就是任何時間都可以開始。要計算出最多可以完成多少件工作。
耗時短的工作當然比長的好，但因為deadline的限制，也不能從短的挑。我們根據deadline由小到大將工作排序，逐一考慮在每個可能deadline之前能完成的工作。用一個max-heap PQ維護以下**迴圈不變性：PQ內是目前dealine之前可以完成的最多件工作，若相同工作數則為其中總工時最小的。**
只要我們能確保維護這個迴圈不變性，根據歸納法，最後的答案就是對的。
當下一個工作(deadline較大)進來時，我們先將它放入PQ，如果總工時不超過此工作的deadline，那此工作是可以完成的，也就沒問題。否則如果總工時過長，我們必須刪除一個工作，此時刪除工時最長的工作顯然是正確的。請留意，根據迴圈不變性，我們最多只需要刪除一個工作。
以下是範例程式，我們放入PQ中的是工作耗時的負值，以便彈出最大值，第10行彈出時用加的其實是減去該值。時間複雜度$O(n\log n)$，因為排序與heap操作。
```python=
class Solution:
def scheduleCourse(self, courses: List[List[int]]) -> int:
courses.sort(key=lambda x: x[1]) # by deadline
total = 0 # total length in pq
pq = [] # shortest jobs can be done
for length,last in courses:
heapq.heappush(pq,-length) # minus for max-heap
total += length
if total>last: # too many job
total += heapq.heappop(pq) # minus largest
return len(pq)
```
[(題目連結) 871. Minimum Number of Refueling Stops (Hard)](https://leetcode.com/problems/minimum-number-of-refueling-stops/)
有一台車從起點要到終點，沿路在某些位置(以距離起點的里程數表示)可以停下來加若干油，車子的油箱無容量限制，請問最少要停下來加油幾次，或者無法到達。
既然油箱是沒有限制的，假設在某個距離$d$以內我們需要加$k$次油，那麼當然應該在$\leq d$的範圍內挑選最多油的$k$個加油站。現在我們一開始並不知道在某個加油站是否要加油。
我們將可以走的距離total的值由小到大推，將目前可以加油的油量放入一個max-heap中維護。每次取出最大值(最多的油)，更新total，並將新增可到達的加油站納入max-heap。直到到達終點，或者沒有加油站在可以到達的範圍內。
以下是範例程式，其中reach是個max-heap，放的是負值，時間複雜度$O(n\log n)$。
```python=
class Solution:
# greedy, refuel the reachable max
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
total = startFuel
stop = 0
reach = [] # pq
i = 0 # index of station
n = len(stations)
while total < target:
# include all reachable stations
while i<n and stations[i][0]<=total:
heapq.heappush(reach,-stations[i][1]) # max heap
i += 1
if reach: # refuel the reachable max
total -= heapq.heappop(reach) # minus value
stop += 1
else: return -1
#end while
return stop
```
[(題目連結) 1606. Find Servers That Handled Most Number of Requests (Hard)](https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/)
這個題目是一個模擬排程的題目，給你已經依照到達時間排序的$n$個工作，每個工作有需要處理的時間。題目指定了以下的排程方式將工作指派給$k$個伺服器，請找出最後處理了最多工作的那些伺服器編號。排程的方法為：
第$i$個工作到達時，由$i\%k$開始往後找第一個空閒的伺服器，如果往後找不到，就再從編號0開始。若所有伺服器都在忙碌狀態，就放棄該工作。否則就指派給第一個找到的空閒伺服器。
我們就是要模擬。但是不能一個一個找。我們可以準備一個容器，存放目前有空閒的伺服器編號。另外要記錄每一台伺服器何時會完成目前的工作而變得空閒。當第$i$個工作在時間$t$到達時：
1. 先檢查哪些伺服器由忙碌變成空閒，將它們加入空閒的容器。
2. 在空閒的伺服器容器中找到$i%k$之後第一個編號。
紀錄完成時間可以用min-heap，這樣可以有效率的找出所有完成時間$\leq t$的伺服器。但是要用什麼容器來放空閒伺服器編號呢？這個容器必須支援新增刪除，並且能快速找到$\geq p$的最小值。在C\++中的set/map就是這樣一個容器，其底層是個二元搜尋樹。
Python新版有個模組名為sortedcontainers，裡面有個SortedList()可以做這件事，其實它的功能比C++的set/map還要多。
有了這個容器程式就簡單了，以下是範例程式。第5行avail就是一個SortedList，初始放的是0 ~ $k-1$。我們另外準備一個list cnt用來記錄每台伺服器的工作數量，另外準備一個min-heap ftime用來放每台忙碌機器的完成時間。
第8行的while迴圈把完工的伺服器編號$s$從heap中取出，用avail.add($s$)放入avail中。第12行$j=i\%k$是要開始找的編號，第13行用avail.bisect_left($j$)找$\geq j$的第一個，名稱與二分搜模組是一樣的，回傳的是index，如果找不到回的是長度，所以找不到的話，我們從頭再找一次(第15行)。取用它的內容與list一樣用avail[idx]，刪除就用avail.pop(idx)。每個操作的時間都是$O(\log k)$。最後，我們將工作最多的伺服器編號取出回傳(第21 ~ 22行)。
整體的時間複雜度是$O(n\log k)$。
```python=
from sortedcontainers import SortedList
class Solution:
def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
cnt = [0]*k # num of processed jobs
avail = SortedList(range(k)) # available servers
ftime = [(1000000001,-1)] # heap of free time and server
for i,t in enumerate(arrival):
while ftime[0][0] <= t:
_,s = heappop(ftime)
avail.add(s)
if len(avail)==0: continue # drop job
j = i%k
idx = avail.bisect_left(j)
if idx==len(avail):
idx = avail.bisect_left(0)
p = avail[idx]
cnt[p] += 1
avail.pop(idx)
heappush(ftime,(t+load[i],p))
#end for
imax = max(cnt)
ans = [i for i in range(k) if cnt[i]==imax]
return ans
```
不使用SortedList可不可做呢？因為指派機器是依照順序的，其實並不難做到，除了放完成時間的heap ftime之外，我們再用兩個heap來放空閒的伺服器：back放的是目前編號小於(curr=i%k)的空閒伺服器，front放編號$\geq$ curr的。以下是範例程式。
第10行如果curr跑回頭，這時我們將front與back對調。第11行跟前面的程式一樣，我們把工作完成的伺服器從ftime中拿出來，根據它的編號，放入back或front中。然後先在front中找最小，如果front是空的就在back中找最小，如果都沒有就放棄此工作。時間複雜度一樣是$O(n\log k)$，不過前一個方法比較直覺，後面這個方法需要動腦筋想一想。資料結構就是工具，工具多的時候，方法就可以比較直接，工具少就要多動腦筋。
```python=
#using only heap
class Solution:
def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
cnt = [0]*k # num of processed jobs
back = list(range(k)) # available servers <i
front = [] # available server >=i
ftime = [(1000000001,-1)] # heap of free time and server
for i,t in enumerate(arrival):
curr = i%k
if curr==0: front,back = back,front
while ftime[0][0] <= t:
_,s = heappop(ftime)
if s>= curr:
heappush(front,s)
else: heappush(back,s)
if front:
p = heappop(front)
elif back:
p = heappop(back)
else: continue # drop job
cnt[p] += 1
heappush(ftime,(t+load[i],p))
#end for
imax = max(cnt)
ans = [i for i in range(k) if cnt[i]==imax]
return ans
```
## 貪心搭配二分搜
「對答案二分搜」是程式算法解題常用的技巧。遇到一個問題時，比較直覺的是順向思考：如何由輸入經過操作變成答案。但在值域(可能的答案)有限的狀況下，我們也可以採取「猜測答案後驗證」的方式來搜尋答案。
如果毫無特性，這將淪為暴搜枚舉的方式。有一類題目，答案的某個特性具有單調性，我們就可用二分搜的方式來快速收斂答案。這一類問題的檢驗程序常常會是一個貪心算法或是掃描算法，所以通常會是貪心搭配二分搜。
這樣講有些抽象，看下面的例題會比較清楚。
[(題目連結) 410. Split Array Largest Sum (Hard)](https://leetcode.com/problems/split-array-largest-sum/)
我們要將一個非負整數陣列切成$k$段連續子陣列，希望最大那一段的總和越小越好。
這一題給的$k$很小，所以其實有DP的解法，但我們直接來看比較好的二分搜解法
一個很明顯的單調性：切的段數$k$越大，切出來的最大段只會越小或一樣，但絕對不會反而變大。因此我們可以對**最大段的總和**來做二分搜。
寫一個函數來驗證給定$lim$值，判斷該陣列是否能切割成不超過$k$個子陣列且每個大小不超過$lim$。想像我們將$lim$由小到大逐一增加，丟去驗證的結果將會是
[False, False, ..., False, True, ...True]
因為一旦某個$lim$值是可以切成功的話，對於更大的值也一定可以切成功。既然滿足此單調性，我們就可以用二分搜來找到第一個True的值，而不必一一去嘗試。
如何寫這個驗證函數呢？因為子陣列必須是連續的，很顯然是個貪心策略：能塞盡量塞，超過限制不得已才切。過程中如果超過$k$段就回傳False，如果可以全部裝完，就回傳True。
至於二分搜的部分有多種寫法，教科書中比較多的是維護一個區間的寫法，筆者比較喜歡寫以下**跳躍二分搜**的寫法，因為在面對不同二分搜的情境時，這個寫法的邏輯比較清楚不容易寫錯，以下就看範例程式來加以介紹。
第4 ~ 12行是驗證函數，這個應該不必再多解釋細節，旦這裡我們假設傳過來的$lim\geq \max(nums)$，否則是必然無解的。二分搜的部分從第16行開始。我們維護一個目前的值$curr$，他將會是無法切割成功的最大值，最後$curr+1$就是我們的答案(可以成功的最小值)。另外維護一個跳躍值$jump$，這個值會逐次減半。每次我們要檢查$curr+jump$是否滿足$curr$的定義(本題的定義是不能切割)，能跳就跳，當$jump$降到0時，$curr$就收斂到最大值了。
一開始的$curr$初值必須放一個不可能成功的值，因為子陣列的大小至少必須是陣列元素最小值，而且必須至少是平均值，這裡我們取兩者較大的值減一。
時間複雜度$O(n\log R)$，$R$是二分搜值域的大小。
```python=
class Solution:
# binary search
def splitArray(self, nums: List[int], k: int) -> int:
# assume lim >= max(nums)
def check(lim,k): # if possible cut with sum <=lim
cut = isum = 0
for p in nums:
isum += p
if isum>lim: # need to cut
cut += 1
isum = p
if cut>= k: return False
return True
total = sum(nums)
if k==1: return total
curr = max(total//k,max(nums)) - 1 # impossible small
jump = total//2
while jump:
while curr+jump<total and not check(curr+jump,k):
curr += jump
jump >>=1
#end while
return curr+1
```
[(題目連結) 1802. Maximum Value at a Given Index in a Bounded Array (Medium)](https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/)
題目是說要建構一個長度$n$且總和不超過$maxSum$的**正整數**陣列，相鄰元素差值不得超過1，要求在指定的$index$位置的元素最大值。這可以想像是小朋友堆一排積木，有$maxSum$塊立方體積木，相鄰座標的高度差不得超過1的條件下，位置$index$最高可以堆多高。
想要直接計算出最大高度不太容易。倒過來逆向思考：高度$h$至少需要多少積木？這顯然是個貪心策略的問題，在$index$高度是$h$，其他位置要盡可能的少，相鄰高度差不得超過1，那只有向兩邊逐步遞減。如同下面的圖示。
所以他只不過是兩個等差級數，左邊一個，右邊一個，可以根據$h$與$index$以及$n$(與兩邊的距離)計算出來最小用量。
會算「給定高度的最小總和」的話，那麼原題目「給定總和限制下的最高高度」如何計算呢？
總和越大可以堆出的高度越高(非遞減)。所以可以二分搜。
以下是範例程式，我們動一點小技巧。先把$maxSum$減去$n$是每個位置先給一個積木，因為題目要求所有位置至少要1，減去之後只要$\geq 0$就可以了，最後回傳答案時在加上1。
第6行的req(h)定義一個函數計算高度$h$的最小總和，內容是兩個等差級數的梯型公式。第13開始是二分搜。跟前一題一樣，這是筆者喜歡的跳躍二分搜型式。$curr$是目前可以達到的最大高度，能增加就增加，最後就是答案。跳躍距離每次減半逐漸收斂。
時間複雜度$O(\log R)$，$R$高度的數值範圍。
```python=
class Solution:
# + ...+(h-1)+h+(h-1)+...+
def maxValue(self, n: int, index: int, maxSum: int) -> int:
maxSum -= n # 1 for each cell
if maxSum<2: return maxSum+1
def req(h): # min sum for height h; h in left part
left = h*(h+1)//2 if index>=h-1 else \
(h+h-index)*(index+1)//2
right = h*(h-1)//2 if n-1-index>=h-1 else \
(h-1+h-(n-1-index))*(n-1-index)//2
return left+right
# binary search
curr = 0
jump = maxSum//2
while jump:
while req(curr+jump) <= maxSum:
curr += jump
jump >>= 1
return curr+1
```
[(題目連結) 2616. Minimize the Maximum Difference of Pairs (Medium)](https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/)
在這題裡，我們要在一群數字中找出$p$對數字，使得每一對差值的最大值越小越好，每一個元素不能配兩次。
例如$nums = [10,1,2,7,1,3]$而$p = 2$。我們可以配$(1,1)$與$(2,3)$，差值分別是0與1，最大差值是1。這裡的$(1,1)$是原來有兩個1。
如果是全部都要配對($n=2p$)我們會怎麼做呢？眾所皆知，在一個排好序的序列中，與其中任何一數最接近的一定出現在他的左右。所以如果每一個數都要配對，就排序後兩兩一組就是最佳答案。
雖然現在並非全部都要參與配對，不過仍然可以發現一定有一組最佳解，其中的每一組配對都是排序後的相鄰元素。理由很簡單，如果不是，可以做替換或兩組交換伴侶，相鄰對的差值只會變小不會更大。
因為不是全部要配，問題是哪些要選進來。
同樣的，我們反過來逆向思考，如果給定配對的差值限制，也就是每一對的差值不得超過某數$v$，我們能否計算出「這一群數字可以配多少對」呢？這是一個貪心策略中一路掃過去就可以解決的問題。看下面的示意圖就很容易了解。
數線上有若干點，相鄰距離$\leq v$的就畫出連接線，$>v$就不畫線。我們要找最大配對數，從左往右，能配就拿去配就是最佳解，當然如果左端已經跟前面配了，這一點就只能跟後面配或者放棄。貪心可以得到最佳解的原因是因為：如果連續偶數個點，就是全都配，如果連續奇數個點，反正有一點要放棄。
以下是範例程式，第4行先排序，然後我們把相鄰差值先求出來放在$s$中備用。第7行開始的函數enough($v$)用貪心策略計算差值$v$以內能否配出至少$p$對。第16行開始二分搜，一樣是跳躍二分搜，此處$curr$的定義是「不足以配出$p$對的最大差值」，所以最後的答案是$curr+1$。在第16行先驗證0是否足夠，然後就從$curr=0$當初始值。
時間複雜度$O(n\log n+n\log R)$，$R=\max(nums)$。
```python=
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
if p==0: return 0
nums.sort()
s = [nums[i]-nums[i-1] for i in range(1,len(nums))]
n = len(s) # to find p non-adjacent in s
def enough(v): # if <= v is enough
i,cnt = 0,0
while i<n and cnt<p:
if s[i]<=v:
cnt += 1
i += 2
else: i += 1
return cnt>=p
# binary search
if enough(0): return 0
curr = 0 # the max not enough
oo = max(s)
jump = oo//2
while jump:
while curr+jump<oo and not enough(curr+jump):
curr += jump
jump >>= 1
return curr+1
```
## 其他類型
[(題目連結) 11. Container With Most Water (Medium)](https://leetcode.com/problems/container-with-most-water/)
這題是說，在每一個位置$i$都有一個高度$h[i]$的隔板，要選擇左右兩個位置$i<j$的隔板來形成一個容器，使得容量$(j-i)\times \min\{ h[i], h[j]\}$越大越好。
直覺來看，我們可以想像一條水平線從無限高度往下降，降到高度$h$時，浮出此水平線的隔板，就是可以hold住高度$h$的，此時取出最左邊與最右邊的位置，就是可以擁有高度$h$的最大區間。對於每個$h$計算一個值並取其中的最大就是答案。以下是這樣做的程式，事實上，新出現的隔板如果不是最左端也不是最右端，可以放棄不必算。
```python=
class Solution:
def maxArea(self, height: List[int]) -> int:
area=0
p = sorted(enumerate(height),reverse = True,key=lambda x: x[1])
left = right = p[0][0]
for i,h in p[1:]:
if i<left:
area = max(area, (right-i)*h)
left = i
elif i > right:
area = max(area, (i-left)*h)
right = i
return area
```
時間複雜度是$O(n\log n)$，因為需要排序。
上面的想法是從高度著手，所以需要排序。以下是另外一種想法，從水平位置著手，可以省掉排序。是個有趣的$O(n)$算法，關鍵是由兩端往中間貪心的掃過去。
一開始先取整個區間$[0,n-1]$，這當然是水平距離最大的區間，但是垂直高度也許很低。我們逐步提高高度，因為高度是取左右兩端的較小值，只移動比較高的一端顯然無用，所以每一次把左右端高度較小的往中間移動，移動到下一個高度較大者，其實每移動一步都算一次也無妨。實作程式時我們左右兩端都寫一個while來找下一個高度大於目前高度$h$的位置，而不必比較左右哪一個比較小。
這相當於雙指針的做法，時間複雜度是$O(n)$。
```python=
class Solution:
def maxArea(self, height: List[int]) -> int:
area,n = 0, len(height)
left,right = 0,n-1
h = min(height[0],height[-1]) # current height
while left < right:
area = max(area, (right-left)*h)
while left<right and height[left]<=h:
left += 1
while left<right and height[right]<=h:
right -= 1
h = min(height[left],height[right])
return area
```
下面這題是有些難度的題目。
[(題目連結) 321. Create Maximum Number (Hard)](https://leetcode.com/problems/create-maximum-number/description/)
題目是說一個陣列可以看成是一個整數的每一個位數的序列，例如$[5,0,0,1,3]$就表示50013。現在有兩個陣列，各自代表一個整數(陣列元素均為0 ~ 9的數字)，要從兩個陣列各取一個subsequence來**合併**組成一個總長度為$k$的序列來代表一個整數，請問此數最大是多少。所謂的subsequence合併是指同一個序列中成員的前後關係不能顛倒。
例如$nums1 = [3,4,6,5]$, $nums2 = [9,1,2,5,8,3]$, $k = 5$，所能取出的最大整數為$[9,8,6,5,3]$，其中$[9,8,3]$來自$nums2$，而$[6,5]$來自$nums1$。
我們先考慮一個比較簡單的版本，給你兩個序列，不用挑選，每一個數字都必須使用，要合併兩序列組成一個最大的數。
乍看之下，很像是兩個sorted list的合併，每次挑兩邊第一個較大的就是對的，但事實不然，問題出在兩邊一樣的時候不能隨便挑。例如53與57，我們必須先跳57的5。所以簡單的解決方法就是每次要比較兩個序列(不能只比頭端)，讓較大者的第一個先拿出來。
那麼「只取$k$而非全部」這件事要怎麼處理呢？我們嘗試各種長度的組合：$nums1$拿出$i$個，$nums2$取$k-i$個，對各種可能的長度$i$都做一次。剩下的問題是對於一個序列，給定長度$i$之下，如何取出最大的數字。
假設有一個數字54372，我們要刪掉一個數字讓剩下的最大，應該怎麼做？越前面的越重要，所以應該刪掉第一個可以讓數字變大的位置，也就是第一個上升的位置，如果沒有上升就刪最後一個。所以54372要刪3變成5472，如果是98763就變成9876。
當長度$n$要刪掉$n-i$個變成$i$個的時候，我們可以重覆以上程序但每一次不必重頭找，因為刪除上一個的時候，我們已經找到第一個上升位置。實作時，我們可以這樣做，由前往後歷遍，在每一個數字時，如果前方比較小而且後面的個數還足夠，就刪除前一個。刪除完畢後將該數字加入。最後的長度也可能超過，就只留下需要的長度。
以下是範例程式，時間複雜度$O(n^3)$，但merge中的比較如果不是每次都比到最後，跑起來沒這麼壞。這個程式看起來可以優化，但可能寫起來會很麻煩。
```python=
class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
def build(num,t): # max of length t from num
res = [10]
n = len(num)
for i,d in enumerate(num):
while res[-1]<d and len(res)-2+n-i>=t:
res.pop()
res.append(d)
return res[1:1+t]
def merge(p,q): # merge two seq as large as possible
res = []
m,n = len(p),len(q)
i,j = 0,0
while i<m and j<n:
if p[i:] > q[j:]:
res.append(p[i])
i += 1
else:
res.append(q[j])
j += 1
return res+p[i:]+q[j:]
#
largest = [0]
for n1 in range(max(0,k-len(nums2)),min(k,len(nums1))+1):
s1,s2 = build(nums1,n1),build(nums2,k-n1)
# print(s1,s2)
s = merge(s1,s2)
largest = max(largest,s)
return largest
```
[(題目連結) 517. Super Washing Machines (Hard)](https://leetcode.com/problems/super-washing-machines/)
有$n$台洗衣機排成一列，每台中有若干衣服，每次可以選擇任意某些洗衣機，將這些機器中的一件衣服移到隔壁台，請問最少幾次可以讓每台機器的衣服上量變成一樣多。請注意，每一次可以移出很多台的衣服，但每台只能移出一件。
首先我們可以很容易算出最後的平均值$avg$，如果總數不能平均分配，那必然是無解。
既然洗衣機是排成一列，我們觀察相鄰兩台($i$與$i+1$)之間，必然存在一個最佳解，在此邊界上只有右移或左移，但不會既有往左移動又有往右移動的狀況。事實上，若前$i$台的初始總數$prefix[i]>avg\times i$，那麼必有一最佳解往右移動了$prefix[i] - avg\times i$件衣服。
如果右邊的衣服總數過多需要往左邊移動，狀況是類似的。
這裡有個疑問是，如果要從$i$移動$q$件到$i+1$，是否必然可以在$q$個回合完成？因為第$i$台有可能一開始只有$0$件衣服。這個疑問是真實可能存在的，不過，如果這個邊界是所有邊界中此差值的最大值，就不會發生這個狀況，假如第$i$台初始是0，那麼$i-1$與$i$之間的需要移動值會大於$i$與$i+1$之間的需要移動值。
所以答案就是找相鄰切割界限上的最大移動需求值。
但是剛才我們推論的是由兩邊往中間傳送的情形，有一個情況疏漏掉了。如果有一台機器初始的衣服很多，左右兩邊都需要他的衣服，那麼，因為一次只能向左或向右移動一件。所以答案不能小於他的移出量。
範例程式很簡單，時間複雜度$O(n)$，$n$是機器數量。
```python=
class Solution:
def findMinMoves(self, machines: List[int]) -> int:
prefix,n = 0,len(machines)
total = sum(machines)
avg = total//n
if avg*n != total: return -1
imax = 0
for i,q in enumerate(machines,start=1):
prefix += q
imax = max(imax, abs(i*avg-prefix), q-avg)
return imax
```
[(題目連結) 316. Remove Duplicate Letters (Medium)](https://leetcode.com/problems/remove-duplicate-letters/description/)
在這題裡，我們將一個字串中重覆的字元刪除，使得每個出現的字元都只出現一次，這樣的字串可能很多，需要找出字典序(lexcidographic order)最小的字串。
刪除重覆字元不難，問題在字典序最小。這題與前面
合併兩數字題目中用到的一個程序(在一個序列中找出一個長度$i$的最大子序列是類似的。
我們先統計每一個字元出現的次數。由前往後歷遍每個字元，答案暫時存放在一個list ans中，當目前看到的字元是$c$的時候，先看看$c$是否已經出現在ans中，若是，則丟棄它並繼續下一個字元。若$c$尚未在ans中，我們由後往前檢查ans，若最後一個字元ans[-1]比$c$小，且後面還有ans[-1]的時候，就把它刪除掉。
以下是範例程式，時間複雜度$O(n)$。
```python=
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
cnt = Counter(s)
occ = set() # if occur in ans
ans = ['$']
for c in s:
cnt[c] -= 1
if c in occ: continue
while ans[-1]>c and cnt[ans[-1]]>0:
occ.remove(ans.pop()) # remove last
ans.append(c)
occ.add(c)
#
return "".join(ans[1:])
```
## 結語
所謂貪心演算法(Greedy algorithm)指的是：一個算法由一連串的決定組成，每次決定時都以當時最有利的方式挑選，而且一旦挑選後就不再更改。Greedy algorithm是算法中一個常用的策略，通常很直覺，如果要保證求出來的是最佳解，必須要證明。證明的方法往往就是證明它每一步的決策都是正確的，也就是存在某一個最佳解的演算法做了相同的決策。
在非解題的實際應用裡，也常常會使用到貪心算法，這時候它可能只是用來做局部調整的程序，或者是找到還不錯但不一定是最佳的解。
貪心算法跟其他很多單元都有關聯，例如之前的sorting與priority queue，以及下一個單元要討論的monotonic stack。
Sign in with Wallet
Connect another wallet