[[437587]]

在二維空間中有許多球形的氣球。對(duì)于每個(gè)氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標(biāo)。由于它是水平的，所以縱坐標(biāo)并不重要，因此只要知道開始和結(jié)束的橫坐標(biāo)就足夠了。開始坐標(biāo)總是小于結(jié)束坐標(biāo)。

一支弓箭可以沿著 x 軸從不同點(diǎn)完全垂直地射出。在坐標(biāo) x 處射出一支箭，若有一個(gè)氣球的直徑的開始和結(jié)束坐標(biāo)為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會(huì)被引爆。可以射出的弓箭的數(shù)量沒有限制。弓箭一旦被射出之后，可以無限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。

給你一個(gè)數(shù)組 points ，其中 points [i] = [xstart,xend] ，返回引爆所有氣球所必須射出的最小弓箭數(shù)。

示例 1：

• 輸入：points = [[10,16],[2,8],[1,6],[7,12]]
• 輸出：2
• 解釋：對(duì)于該樣例，x = 6 可以射爆 [2,8],[1,6] 兩個(gè)氣球，以及 x = 11 射爆另外兩個(gè)氣球

示例 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

思路

如何使用最少的弓箭呢?

直覺上來看，貌似只射重疊最多的氣球，用的弓箭一定最少，那么有沒有當(dāng)前重疊了三個(gè)氣球，我射兩個(gè)，留下一個(gè)和后面的一起射這樣弓箭用的更少的情況呢?

嘗試一下舉反例，發(fā)現(xiàn)沒有這種情況。

那么就試一試貪心吧!局部最優(yōu)：當(dāng)氣球出現(xiàn)重疊，一起射，所用弓箭最少。全局最優(yōu)：把所有氣球射爆所用弓箭最少。

算法確定下來了，那么如何模擬氣球射爆的過程呢?是在數(shù)組中移除元素還是做標(biāo)記呢?

如果真實(shí)的模擬射氣球的過程，應(yīng)該射一個(gè)，氣球數(shù)組就remove一個(gè)元素，這樣最直觀，畢竟氣球被射了。

但仔細(xì)思考一下就發(fā)現(xiàn)：如果把氣球排序之后，從前到后遍歷氣球，被射過的氣球僅僅跳過就行了，沒有必要讓氣球數(shù)組remote氣球，只要記錄一下箭的數(shù)量就可以了。

以上為思考過程，已經(jīng)確定下來使用貪心了，那么開始解題。

為了讓氣球盡可能的重疊，需要對(duì)數(shù)組進(jìn)行排序。

那么按照氣球起始位置排序，還是按照氣球終止位置排序呢?

其實(shí)都可以!只不過對(duì)應(yīng)的遍歷順序不同，我就按照氣球的起始位置排序了。

既然按照起始位置排序，那么就從前向后遍歷氣球數(shù)組，靠左盡可能讓氣球重復(fù)。

從前向后遍歷遇到重疊的氣球了怎么辦?

如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區(qū)間一定需要一個(gè)弓箭。

以題目示例：[[10,16],[2,8],[1,6],[7,12]]為例，如圖：(方便起見，已經(jīng)排序)

用最少數(shù)量的箭引爆氣球

可以看出首先第一組重疊氣球，一定是需要一個(gè)箭，氣球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; 
    } 
}; 

• 時(shí)間復(fù)雜度O(nlogn)，因?yàn)橛幸粋€(gè)快排
• 空間復(fù)雜度O(1)

可以看出代碼并不復(fù)雜。

注意事項(xiàng)

注意題目中說的是：滿足 xstart ≤ x ≤ xend，則該氣球會(huì)被引爆。那么說明兩個(gè)氣球挨在一起不重疊也可以一起射爆，

所以代碼中 if (points[i][0] > points[i - 1][1]) 不能是>=

總結(jié)

這道題目貪心的思路很簡單也很直接，就是重復(fù)的一起射了，但本題我認(rèn)為是有難度的。

就算思路都想好了，模擬射氣球的過程，很多同學(xué)真的要去模擬了，實(shí)時(shí)把氣球從數(shù)組中移走，這么寫的話就復(fù)雜了。

而且尋找重復(fù)的氣球，尋找重疊氣球最小右邊界，其實(shí)都有代碼技巧。

貪心題目有時(shí)候就是這樣，看起來很簡單，思路很直接，但是一寫代碼就感覺賊復(fù)雜無從下手。

這里其實(shí)是需要代碼功底的，那代碼功底怎么練?

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。