题解 | #牛客泡泡堂#

方法一 暴力求解（超时）

我们想要知道炸弹放在哪里炸死人数最多，那么我们遍历可以放置炸弹的每个位置 ，然后计算该位置可以炸死多少玩家，然后对炸死人数进行比较，最后返回最大值即可。但是是会超时的。

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param Player Point类vector Player
     * @return int整型
     */
    int BoomKill(int n, int m, vector<Point>& Player) {
        int ans = 0;
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                // 在 (i, j) 位置放炸弹，观察能炸死多少玩家
                int count = 0;
                for(Point player : Player) {
                    // 判断是否会被炸死，其中 xleft 和 xright 是 x 方向上会被炸死的范围
                    int xleft = max(1, i - m + 1), xright = min(n, i + m - 1);
                    if(player.x == i || player.y == j && player.x >= xleft && player.x <= xright)
                        count ++;
                }
                ans = max(ans, count);
            }
        }
        return ans;
    }
};

时间复杂度：， 为玩家数量，遍历地图上每一个位置时间复杂度为 ，然后需要判断有多少个玩家会被炸死，所以总的时间复杂度为 。

空间复杂度：，并未申请额外空间。

方法二 反向思路（内存超限）

我们放置炸弹炸死玩家，反过来我们可以思考某个玩家可以被放在哪些位置的炸弹炸死。但是会内存超限。

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param Player Point类vector Player
     * @return int整型
     */
    int BoomKill(int n, int m, vector<Point>& Player) {
        int ans = 0;
        // 记录下在每个位置放置炸弹可以炸死多少玩家
        vector<vector<int>> nums(n + 1, vector<int>(n + 1, 0));
        for(Point player : Player) {
            // 玩家可以被炸死的范围
            int xleft = max(1, player.x - m + 1), xright = min(n, player.x + m - 1);
            for(int i = xleft; i <= xright; i ++) {
                nums[i][player.y] ++;
            }
            for(int j = 1; j <= n; j ++) {
                // 为了避免重复计算，重叠部分不计算
                if(j != player.y)
                    nums[player.x][j] ++;
            }
        }
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                ans = max(ans, nums[i][j]);
            }
        }
        return ans;
    }
};

时间复杂度：，首先遍历玩家的过程中时间复杂度为 ，最后会对整个 的范围进行遍历求最大值，时间复杂度为 。
空间复杂度：，我们开辟了 的数组去存储每个位置放置炸弹可以炸死多少玩家。

方法三 最大堆

根据炸弹的威力，我们知道对于同一个 而言，在 方向上能够炸死的玩家是一样的，所以某个 坐标下只要求出在哪个 坐标能够炸死更多的玩家，那么这个就是当前的最优解，然后再求出不同 坐标所对应的数量最大值即可。
但是如果我们使用暴力求解的方法去实现这个思路的话，显然复杂度还是达不到题目要求。

解题思路如下：

1. 首先我们先对玩家进行排序，第一排序指标为 坐标，第二排序指标为 坐标，然后我们就可以寻找不同 坐标所能炸死的最大玩家数量了。
   
2. 因为对于每个 我们要计算 可以炸死的最大玩家数量，那么我们为了缩小时间复杂度，我们自建最大堆来进行存储。
   

   /**
   * struct Point {
   *    int x;
   *    int y;
   *    Point(int xx, int yy) : x(xx), y(yy) {}
   * };
   */
   class HeapVec {
    public:
    // 建堆，其中 count 存储 y 对应的玩家数量，
    // 因为我们在调整堆的时候 y 对应的序号会发生改变
    // 我们使用 heappos[y] 存储 y 在排好序的数组中应该在的位置
    // traceback[idx] 代表在排好序的数组中下标为 idx 的值在 count 中的位置
    vector<int> count;
    vector<int> heappos;
    vector<int> traceback;
    int size;
    // 初始化
    HeapVec(int n) { 
        size = n;
        count.resize(n,0);
        heappos.resize(n,0);
        traceback.resize(n,0);
        for (int i=0; i<n; i++) {
            heappos[i] = i;
            traceback[i] = i;
        }
    }
    int maxCount() {
        // 返回最大值
        return count[traceback[0]];
    }
    // 更新 count[i] 的值
    void updateValue(int i, int flag) {
        count[i] += flag;
        if(flag == 1) siftUp(i);
        else siftDown(i);
    }
    // 上移操作
    void siftUp(int i) {    
        // 已经是最大值，不需要移动
        if (heappos[i] == 0) return;
        // 父节点
        int fa = (heappos[i] - 1)/2;
        // 当前节点大于父节点，与父节点交换位置
        if (count[i] > count[traceback[fa]]){
            int tmp = heappos[i];
            swap(heappos[i], heappos[traceback[fa]]);
            swap(traceback[tmp], traceback[fa]);
            siftUp(i);
        }
    }
    // 下移操作
    void siftDown(int i) {
        // 左右子节点
        int left = heappos[i] * 2 + 1, right = left + 1;
        // 求左右子节点较大值
        int large = left;
        if (left >= size) return;
        if(right < size && count[traceback[left]] <= count[traceback[right]])
            large = right;
        // 如果当前节点大于左右子节点，不需要移动
        if (count[i] >= count[traceback[large]]) return;
        else {
            // 和更大的子节点交换位置
            int tmp = traceback[large];
            swap(traceback[large], traceback[heappos[i]]);
            swap(heappos[i], heappos[tmp]);
            siftDown(i);
        }
    }
   };
   class Solution {
   public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param Player Point类vector Player
     * @return int整型
     */
    int BoomKill(int n, int m, vector<Point>& Player) {
        int ans = 0;
        // 对玩家进行排序
        sort(Player.begin(), Player.end(), [](Point p1, Point p2) {
            return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
        });
        // l, r 为操作过的数据范围
        int l = -1, r = 0;
        int cur = 0, next = 0, pre = 0, cnt = 0;
        int num = Player.size();
        HeapVec hv(n + 1);
        while(cur < num) {
            int x = Player[cur].x;
            cnt = 0;
            // 计算当前 x 所在列有多少玩家，并更新下一个要操作的 x 坐标 next
            while(next < num && Player[next].x == Player[cur].x) {
                next ++; cnt ++;
            }
            // 如果 Player[l] 已经不在爆炸范围内，将对应的 count 值减一，同时 l 边界右移
            while(l + 1 < pre && Player[l + 1].x < x - m + 1) {
                l ++;
                hv.updateValue(Player[l].y, -1);
            }
            // 如果上一个操作的x 坐标不在爆炸范围内，那么更新左边界
            if(Player[pre].x < x - m + 1) {
                l = next - 1;
            } else {
                // 因为计算 count 值没计算 x 所在列，所以需要将 pre 所在列对应的 count 值加一
                for(int i = pre; i < cur; i ++)
                    hv.updateValue(Player[i].y, 1);
            }
            // 更新 pre
            pre = cur;
            // 如果 cur 在上一次已经操作过（即加过一），因为我们不能将 cur 所在列对应的 count 值加一，所以要将 cur 所在列对应的 count 值减一
            if(cur < r) {
                for(int i = cur; i < next; i ++) 
                    hv.updateValue(Player[i].y, -1);
            }
            // 更新 r 边界
            r = max(r, next);
            // 如果 Player[r] 在爆炸范围内，将对应的 count 值加一，同时 r 边界右移
            while(r < num && Player[r].x <= x + m - 1) {
                hv.updateValue(Player[r].y, 1);
                r ++;
            }
            ans = max(ans, cnt + hv.maxCount());
            cur = next;
        }
        return ans;
    }
   };

   时间复杂度：，排序时间复杂度为 ，尽管我们存在多个循环，但是基本上是对所有的 player 遍历了一遍，然后每个 值在堆中 siftUp 和 siftDown 的时间复杂度都为 ，所以总的时间复杂度为 ，
   空间复杂度：，我们只开辟了 count、heappos、traceback 三个数组，考虑到 siftUp 和 siftDown 的递归调用栈深度，空间复杂度为 。