題目敘述
這題的場景是防禦城市，免於怪獸的入侵。
題目會給定兩個陣列：一個是dist，代表怪獸和城市之間的距離。
一個是speed，代表怪獸每分鐘前進的距離，也就是怪獸的速度。
我們有一把一開始已經充滿電的電動槍，一槍可以擊殺一隻怪獸，擊發後需要耗費一分鐘的冷卻時間讓電動槍再次充滿電。
當怪獸抵達城市的時候，我們就算輸了。
題目要求我們計算最多可以消滅幾隻怪獸？
測試範例
Example 1:
Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.
Example 2:
Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.
Example 3:
Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.
約束條件
Constraints:
n == dist.length == speed.length1 <= n <= 10^51 <= dist[i], speed[i] <= 10^5
演算法
題目已經給我們怪獸的距離，和怪獸的速度。我們可以接著計算出怪獸抵達城市的秒數。
然後，把計算出來的秒數，也就是怪獸抵達城市的先後次序由小到大排序好。
這一步驟用到了排序的觀念。
下一步，為了最大化怪獸擊殺數量，也就是最大化我方存活時間，就是依照怪獸威脅的輕重緩急，也就是怪獸抵達城市的先後次序，我們就按照這個順序去消滅怪獸。
這一步驟用到了Greedy 貪心的觀念，局部最優解導出全局最優解。
最後，當遊戲結束(怪獸已經抵達城市，或者我方率先消滅所有怪獸)時，當下的擊殺數量就是怪獸擊殺數量的最大值。
程式碼
class Solution:
def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
n = len(dist)
# Time of arrival = distance / speed
time_of_arrival = [ d/s for d, s in zip(dist, speed) ]
# Keep time of arrival sorted in ascending order
# And we will shoot monster with this order
time_of_arrival.sort()
# Simulate the shooting process
for i_th_monster in range(n):
# one shot per minute
shooting_time = i_th_monster
if time_of_arrival[i_th_monster] <= shooting_time:
# oops, monster already get into city.
return i_th_monster
# It's safe now, We can emiminate all monsters!
# : )
return n
複雜度分析
時間複雜度:
O( n log n ) 耗費在怪獸秒數(也是怪獸抵達城市的先後次序)的排序上。
空間複雜度:
O(ｎ) time_of_arrival陣列，儲存怪獸抵達城市的秒數，也是抵達城市的先後順序。
關鍵知識點
為了最大化怪獸擊殺數量，也就是最大化我方存活時間，就是依照怪獸威脅的輕重緩急，也就是怪獸抵達城市的先後次序，我們就按照這個順序去消滅怪獸。
這一步驟用到了Greedy 貪心的觀念，局部最優解導出全局最優解。
最後，當遊戲結束(怪獸已經抵達城市，或者我方率先消滅所有怪獸)時，當下的擊殺數量就是怪獸擊殺數量的最大值。
Reference:
