本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實現(xiàn)題解，涉及到通用解法時更將歸納總結出相應的算法模板。
為了方便在PC上運行調試、分享代碼文件，我還建立了相關的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結等，還可以看到原題出現(xiàn)頻率和相關企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。
由于本系列文章的內(nèi)容隨時可能發(fā)生更新變動，歡迎關注和收藏征服LeetCode系列文章目錄一文以作備忘。
你正在玩一款電子游戲，在游戲中你需要保護城市免受怪物侵襲。給你一個?下標從 0 開始?且長度為?n?的整數(shù)數(shù)組?dist?，其中?dist[i]?是第?i?個怪物與城市的?初始距離（單位：米）。
怪物以?恒定?的速度走向城市。給你一個長度為?n?的整數(shù)數(shù)組?speed?表示每個怪物的速度，其中?speed[i]?是第?i?個怪物的速度（單位：米/分）。
怪物從?第 0 分鐘?時開始移動。你有一把武器，并可以?選擇?在每一分鐘的開始時使用，包括第 0 分鐘。但是你無法在一分鐘的中間使用武器。這種武器威力驚人，一次可以消滅任一還活著的怪物。
一旦任一怪物到達城市，你就輸?shù)袅诉@場游戲。如果某個怪物?恰?在某一分鐘開始時到達城市，這會被視為?輸?shù)?/strong>?游戲，在你可以使用武器之前，游戲就會結束。
返回在你輸?shù)粲螒蚯翱梢韵麥绲墓治锏?最大?數(shù)量。如果你可以在所有怪物到達城市前將它們?nèi)肯麥?，返??n?。
示例 1：
輸入：dist = [1,3,4], speed = [1,1,1]
輸出：3
解釋：
第 0 分鐘開始時，怪物的距離是 [1,3,4]，你消滅了第一個怪物。
第 1 分鐘開始時，怪物的距離是 [X,2,3]，你沒有消滅任何怪物。
第 2 分鐘開始時，怪物的距離是 [X,1,2]，你消滅了第二個怪物。
第 3 分鐘開始時，怪物的距離是 [X,X,1]，你消滅了第三個怪物。
所有 3 個怪物都可以被消滅。
示例 2：
輸入：dist = [1,1,2,3], speed = [1,1,1,1]
輸出：1
解釋：
第 0 分鐘開始時，怪物的距離是 [1,1,2,3]，你消滅了第一個怪物。
第 1 分鐘開始時，怪物的距離是 [X,0,1,2]，你輸?shù)袅擞螒颉?你只能消滅 1 個怪物。
示例 3：
輸入：dist = [3,2,4], speed = [5,3,2]
輸出：1
解釋：
第 0 分鐘開始時，怪物的距離是 [3,2,4]，你消滅了第一個怪物。
第 1 分鐘開始時，怪物的距離是 [X,0,2]，你輸?shù)袅擞螒颉?
你只能消滅 1 個怪物。
提示：
n == dist.length == speed.length1 <= n <= 10^51 <= dist[i], speed[i] <= 10^5
解法1 貪心+排序
為了消滅盡可能多的怪物，我方需要堅持盡可能長的時間，因為我方每分鐘都能消滅一個怪物。為了堅持更久，我方需要先消滅先來的怪物。因此，貪心的思路是將怪物的到達時間排序，先消滅到達時間早的怪物。我方的攻擊時間序列是 [ 1 , 2 , 3 , … ? ] [1,2,3,\dots] [1,2,3,…] ，將「我方的攻擊時間序列」和「排序后的怪物到達時間」依次進行比較，當?shù)谝淮纬霈F(xiàn)到達時間小于等于攻擊時間，即表示怪物到達城市，我方會輸?shù)粲螒?/mark>。
在比較時，因為我方的攻擊時間為整數(shù)，因此可以將怪物到達時間向上取整，可以達到避免浮點數(shù)誤差的效果。如果遍歷完序列都沒有出現(xiàn)這種情況，則表示我方可以消滅全部怪物。
class Solution {
public:
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
vector<int> a;
int n = dist.size();
for (int i = 0; i < n; ++i) a.push_back(i);
sort(a.begin(), a.end(), [&](const int &u, const int &v) {
double ma = 1.0 * dist[u] / speed[u];
double mb = 1.0 * dist[v] / speed[v];
return ma < mb;
});
int k = 0;
while (k < n && 1.0 * dist[a[k]] / speed[a[k]] > k) ++k;
return k;
}
};
復雜度分析：
- 時間復雜度： O ( n log ? n ) O(n\log n) O(nlogn)
- 空間復雜度： O ( n ) O(n) O(n)
解法2 貪心+計數(shù)排序
著重講解計數(shù)的思想：每只怪物都有一個最遲被解決的時間 T T T ，小于等于這個時間內(nèi)，玩家可以隨意選擇一個時間去解決，而超過這個時間，怪物就會入侵城市，游戲也宣告失敗。
計數(shù)數(shù)組 c o u n t count count ，就是用來記錄每個最遲被解決的時間 T T T 上有多少個怪物。 T T T 的計算公式是 T = ( d i s t [ i ] ? 1 ) / s p e e d [ i ] T=(dist[i] - 1) / speed[i] T=(dist[i]?1)/speed[i] 。當怪物的最遲被解決的時間 T T T 被計算出來后，對 c o u n t count count 進行 c o u n t [ T ] + + count[T]++ count[T]++ 操作。
有了計數(shù)數(shù)組 c o u n t count count 之后，我們就知道了在每個時刻，需要解決的怪物數(shù)量。這個時候，我們定義一個整數(shù) k i l l kill kill 。表示我們在某個時間內(nèi)能解決怪物的數(shù)量。如果在某個時刻我們能夠解決怪物的數(shù)量 < 我們需要解決的怪物數(shù)量，說明怪物入侵城市，游戲失敗。
k i l l kill kill 的計算規(guī)則也很簡單，一分鐘解決一只怪物，那么 t t t 時刻就能解決 t t t 只怪物。
注意： c o u n t count count 的大小如何確定呢？因為 T T T 的計算結果不確定，如果我們直接定義最大的數(shù)組涵蓋所有情況，又會導致空間的浪費。實際上， c o u n t count count 的大小設定為 n n n 即可，因為怪物一共有 n n n 只，最遲 n n n 時刻內(nèi)就能解決掉所有怪物，所以對于超過 n n n 的 T T T ，我們直接忽略就行。文章來源：http://www.zghlxwxcb.cn/news/detail-698910.html
class Solution {
public:
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
int n = dist.size();
vector<int> count(n, 0); //對每只怪物的最遲消滅時間進行計數(shù)
for(int i = 0; i < n; i++) {
int time = (dist[i] - 1) / speed[i]; //怪物需要在time時間內(nèi)被消滅
if(time < n) //time >= n的怪物不用管
count[time]++;
}
int kill = 0; //能夠擊殺怪物的數(shù)量
for(int i = 0; i < n; i++) {
kill++; //每過一秒能多擊殺一只怪物
kill -= count[i]; //減去限定時間需要擊殺的怪物
if(kill < 0) //如果怪物到達城市
return i + 1;
}
return n;
}
};
復雜度分析：文章來源地址http://www.zghlxwxcb.cn/news/detail-698910.html
- 時間復雜度： O ( n ) O(n) O(n) ，其中 n n n 是數(shù)組 d i s t dist dist 和 s p e e d speed speed 的長度。為兩次遍歷的時間復雜度。
- 空間復雜度： O ( n ) O(n) O(n) 。需要一個數(shù)組保存怪物的到達時間。
到了這里，關于LeetCode 1921. Eliminate Maximum Number of Monsters【貪心,計數(shù)排序】1527的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
