我們一起用最少數量的箭引爆氣球
在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標。由于它是水平的，所以縱坐標并不重要，因此只要知道開始和結束的橫坐標就足夠了。開始坐標總是小于結束坐標。
一支弓箭可以沿著 x 軸從不同點完全垂直地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會被引爆。可以射出的弓箭的數量沒有限制。弓箭一旦被射出之后，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量。
給你一個數組 points ，其中 points [i] = [xstart,xend] ，返回引爆所有氣球所必須射出的最小弓箭數。
示例 1：
- 輸入：points = [[10,16],[2,8],[1,6],[7,12]]
- 輸出：2
- 解釋：對于該樣例，x = 6 可以射爆 [2,8],[1,6] 兩個氣球，以及 x = 11 射爆另外兩個氣球
示例 2：
- 輸入：points = [[1,2],[3,4],[5,6],[7,8]]
- 輸出：4
示例 3：
- 輸入：points = [[1,2],[2,3],[3,4],[4,5]]
- 輸出：2
示例 4：
- 輸入：points = [[1,2]]
- 輸出：1
示例 5：
- 輸入：points = [[2,3],[2,3]]
- 輸出：1
提示：
- 0 <= points.length <= 10^4
- points[i].length == 2
- -2^31 <= xstart < xend <= 2^31 - 1
思路
如何使用最少的弓箭呢?
直覺上來看，貌似只射重疊最多的氣球，用的弓箭一定最少，那么有沒有當前重疊了三個氣球，我射兩個，留下一個和后面的一起射這樣弓箭用的更少的情況呢?
嘗試一下舉反例，發現沒有這種情況。
那么就試一試貪心吧!局部最優：當氣球出現重疊，一起射，所用弓箭最少。全局最優：把所有氣球射爆所用弓箭最少。
算法確定下來了，那么如何模擬氣球射爆的過程呢?是在數組中移除元素還是做標記呢?
如果真實的模擬射氣球的過程，應該射一個，氣球數組就remove一個元素，這樣最直觀，畢竟氣球被射了。
但仔細思考一下就發現：如果把氣球排序之后，從前到后遍歷氣球，被射過的氣球僅僅跳過就行了，沒有必要讓氣球數組remote氣球，只要記錄一下箭的數量就可以了。
以上為思考過程，已經確定下來使用貪心了，那么開始解題。
為了讓氣球盡可能的重疊，需要對數組進行排序。
那么按照氣球起始位置排序，還是按照氣球終止位置排序呢?
其實都可以!只不過對應的遍歷順序不同，我就按照氣球的起始位置排序了。
既然按照起始位置排序，那么就從前向后遍歷氣球數組，靠左盡可能讓氣球重復。
從前向后遍歷遇到重疊的氣球了怎么辦?
如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區間一定需要一個弓箭。
以題目示例：[[10,16],[2,8],[1,6],[7,12]]為例，如圖：(方便起見，已經排序)
用最少數量的箭引爆氣球
可以看出首先第一組重疊氣球，一定是需要一個箭，氣球3，的左邊界大于了 第一組重疊氣球的最小右邊界，所以再需要一支箭來射氣球3了。
C++代碼如下：
- class Solution {
- private:
- static bool cmp(const vector<int>& a, const vector<int>& b) {
- return a[0] < b[0];
- }
- public:
- int findMinArrowShots(vector<vector<int>>& points) {
- if (points.size() == 0) return 0;
- sort(points.begin(), points.end(), cmp);
- int result = 1; // points 不為空至少需要一支箭
- for (int i = 1; i < points.size(); i++) {
- if (points[i][0] > points[i - 1][1]) { // 氣球i和氣球i-1不挨著，注意這里不是>=
- result++; // 需要一支箭
- }
- else { // 氣球i和氣球i-1挨著
- points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重疊氣球最小右邊界
- }
- }
- return result;
- }
- };
- 時間復雜度O(nlogn)，因為有一個快排
- 空間復雜度O(1)
可以看出代碼并不復雜。
注意事項
注意題目中說的是：滿足 xstart ≤ x ≤ xend，則該氣球會被引爆。那么說明兩個氣球挨在一起不重疊也可以一起射爆，
所以代碼中 if (points[i][0] > points[i - 1][1]) 不能是>=
總結
這道題目貪心的思路很簡單也很直接，就是重復的一起射了，但本題我認為是有難度的。
就算思路都想好了，模擬射氣球的過程，很多同學真的要去模擬了，實時把氣球從數組中移走，這么寫的話就復雜了。
而且尋找重復的氣球，尋找重疊氣球最小右邊界，其實都有代碼技巧。
貪心題目有時候就是這樣，看起來很簡單，思路很直接，但是一寫代碼就感覺賊復雜無從下手。
這里其實是需要代碼功底的，那代碼功底怎么練?
本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。
