我將演算法學習相關的資料已經整理到了Github ：https://github.com/youngyangyang04/leetcode-master，裡面還有leetcode刷題攻略、各個型別經典題目刷題順序、思維導圖看一看一定會有所收穫，如果給你有幫助給一個star支援一下吧！
452. 用最少數量的箭引爆氣球題目連結：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
在二維空間中有許多球形的氣球。對於每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束座標。
由於它是水平的，所以縱座標並不重要，因此只要知道開始和結束的橫座標就足夠了。開始座標總是小於結束座標。
一支弓箭可以沿著 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^4points[i].length == 2-2^31 <= xstart < xend <= 2^31 - 1思路如何使用最少的弓箭呢？
直覺上來看，貌似只射重疊最多的氣球，用的弓箭一定最少，那麼有沒有當前重疊了三個氣球，我射兩個，留下一個和後面的一起射這樣弓箭用的更少的情況呢？
嘗試一下舉反例，發現沒有這種情況。
那麼就試一試貪心吧！區域性最優：當氣球出現重疊，一起射，所用弓箭最少。全域性最優：把所有氣球射爆所用弓箭最少。
「演算法確定下來了，那麼如何模擬氣球射爆的過程呢？是在陣列中移除元素還是做標記呢？」
如果真實的模擬射氣球的過程，應該射一個，氣球陣列就remove一個元素，這樣最直觀，畢竟氣球被射了。
但仔細思考一下就發現：如果把氣球排序之後，從前到後遍歷氣球，被射過的氣球僅僅跳過就行了，沒有必要讓氣球陣列remote氣球，只要記錄一下箭的數量就可以了。
以上為思考過程，已經確定下來使用貪心了，那麼開始解題。
「為了讓氣球儘可能的重疊，需要對陣列進行排序」。
那麼按照氣球起始位置排序，還是按照氣球終止位置排序呢？
其實都可以！只不過對應的遍歷順序不同，我就按照氣球的起始位置排序了。
既然按照其實位置排序，那麼就從前向後遍歷氣球陣列，靠左儘可能讓氣球重複。
從前向後遍歷遇到重疊的氣球了怎麼辦？
「如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區間一定需要一個弓箭」。
以題目示例：[[10,16],[2,8],[1,6],[7,12]]為例，如圖：（方便起見，已經排序）
452.用最少數量的箭引爆氣球
可以看出首先第一組重疊氣球，一定是需要一個箭，氣球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; }};可以看出程式碼並不複雜。
注意事項注意題目中說的是：滿足 xstart ≤ x ≤ xend，則該氣球會被引爆。那麼說明兩個氣球挨在一起不重疊也可以一起射爆，
所以程式碼中 if (points[i][0] > points[i - 1][1]) 不能是>=
總結這道題目貪心的思路很簡單也很直接，就是重複的一起射了，但本題我認為是有難度的。
就算思路都想好了，模擬射氣球的過程，很多同學真的要去模擬了，實時把氣球從陣列中移走，這麼寫的話就複雜了。
而且尋找重複的氣球，尋找重疊氣球最小右邊界，其實都有程式碼技巧。
貪心題目有時候就是這樣，看起來很簡單，思路很直接，但是一寫程式碼就感覺賊複雜無從下手。
這裡其實是需要程式碼功底的，那程式碼功底怎麼練？
「多看多寫多總結！」
打算從頭開始打卡的錄友，可以在「演算法彙總」這裡找到歷史文章，很多錄友都在從頭打卡，你並不孤單！
-------end-------
我是程式設計師Carl，個人主頁：https://github.com/youngyangyang04
這裡每天8:35準時推送一道經典演算法題目，我選擇的每道題目都不是孤立的，而是由淺入深，環環相扣，幫你梳理演算法知識脈絡，輕鬆學演算法！