用最少数量的箭引爆气球
思路
如何使用最少的弓箭呢？
直覺上來看，貌似只射重疊最多的氣球，用的弓箭一定最少，那么有沒有當前重疊了三個氣球，我射兩個，留下一個和后面的一起射這樣弓箭用的更少的情況呢？
嘗試一下舉反例，發現沒有這種情況。
那么就試一試貪心吧！局部最優：當氣球出現重疊，一起射，所用弓箭最少。全局最優：把所有氣球射爆所用弓箭最少。
「算法確定下來了，那么如何模擬氣球射爆的過程呢？是在數組中移除元素還是做標記呢？」
如果真實的模擬射氣球的過程，應該射一個，氣球數組就remove一個元素，這樣最直觀，畢竟氣球被射了。
但仔細思考一下就發現：如果把氣球排序之后，從前到后遍歷氣球，被射過的氣球僅僅跳過就行了，沒有必要讓氣球數組remote氣球，只要記錄一下箭的數量就可以了。
以上為思考過程，已經確定下來使用貪心了，那么開始解題。
「為了讓氣球盡可能的重疊，需要對數組進行排序」。
那么按照氣球起始位置排序，還是按照氣球終止位置排序呢？
其實都可以！只不過對應的遍歷順序不同，我就按照氣球的起始位置排序了。
既然按照其實位置排序，那么就從前向后遍歷氣球數組，靠左盡可能讓氣球重復。
從前向后遍歷遇到重疊的氣球了怎么辦？
「如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區間一定需要一個弓箭」。
以題目示例：[[10,16],[2,8],[1,6],[7,12]]為例，如圖：（方便起見，已經排序）
可以看出首先第一組重疊氣球，一定是需要一個箭，氣球3，的左邊界大于了 第一組重疊氣球的最小右邊界，所以再需要一支箭來射氣球3了。
C++代碼如下：
時間復雜度O(nlogn)，因為有一個快排 空間復雜度O(1) class Solution { public:static bool cmp(vector<int> a,vector<int> b){if(a[0]==b[0]) return a[1]<b[1];return a[0]<b[0];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(),points.end(),cmp);int res=1; // points 不為空至少需要一支箭int minLeft=points[0][1];for(int ii=1;ii<points.size();ii++){if(points[ii][0]<=minLeft){minLeft=min(points[ii][1],minLeft);//}else{minLeft=points[ii][1];res++;}}return res;} };優化
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;} };這道題目貪心的思路很簡單也很直接，就是重復的一起射了，但本題我認為是有難度的。
就算思路都想好了，模擬射氣球的過程，如果真的去模擬，就要把氣球從數組中移走，這么寫的話就復雜了。
而且尋找重復的氣球，尋找重疊氣球最小右邊界，其實都有代碼技巧。
貪心題目有時候就是這樣，看起來很簡單，思路很直接，但是一寫代碼就感覺賊復雜無從下手。
這里其實是需要代碼功底的，那代碼功底怎么練？
「多看多寫多總結！」
總結
以上是生活随笔為你收集整理的用最少数量的箭引爆气球的全部內容，希望文章能夠幫你解決所遇到的問題。
