[数据结构与算法]LeetCode 452. 用最少数量的箭引爆气球(贪心算法)

452. 用最少数量的箭引爆气球

贪心算法

思路

首先对数组按照右边界升序排序。我们从第一个气球的右边界开始射箭，寻找气球左边界小于第一个气球右边界的气球（因为这些气球一定会被同时引爆），而当遍历到某个气球的最左侧值大于当前射出的箭最右侧值的时候，我们之前射出的箭并不能解决掉这个气球，这时候就需要一支新的箭在这个不能解决掉的气球的最右侧发射。在这样的贪心策略下（由局部最优（如果当前射出最右侧的箭都不能解决某个气球，才需要一支新的箭）找到全局最优），最终会得到最少的箭数。

代码分析

class Solution
{
public:
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        return a[1] < b[1];
    }
    int findMinArrowShots(vector<vector<int>> &points)
    {
        sort(points.begin(), points.end(), cmp);
        int pre = points[0][1], count = 1;
        for (int i = 1; i < points.size(); i++)
        {
            // 无重叠则开启下一轮
            if (points[i][0] > pre)
            {
                pre = points[i][1];
                count++;
            }
        }
        return count;
    }
};

主要是参考了之前无重叠区间的思想，改写了一下，还是比较顺利的。

复杂度分析

时间复杂度：$O(nlogn)$，其中 $n$ 是数组 $points$ 的长度。排序的时间复杂度为 $O(nlogn)$，对所有气球进行遍历并计算答案的时间复杂度为 $O(n)$，其在渐进意义下小于前者，因此可以忽略。

空间复杂度：$O(logn)$，即为排序需要使用的栈空间。