Leetcode 1921.消灭怪物的最大数量

Leetcode 算法

Leetcode

发布日期: 2023-09-07

更新日期: 2023-09-07

文章字数: 1.2k

阅读时长: 4 分

阅读次数:

Leetcode 1921. 消灭怪物的最大数量

概要：本题是在比较孤傲五移动的次数和我们可以走的次数，其中需要判断的是每一次移动之后，怪物移动的距离是否会比人移动的次数多。这里重要的思想是移动的次数问题，需要满足取余的思想

1. 题目说明

你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ，其中 dist[i] 是第 i 个怪物与城市的 初始距离（单位：米）。
怪物以恒定的速度走向城市。给你一个长度为 n 的整数数组 speed 表示每个怪物的速度，其中 speed[i] 是第 i 个怪物的速度（单位：米/分）。
怪物从 第 0 分钟 时开始移动。你有一把武器，并可以选择在每一分钟的开始时使用，包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人，一次可以消灭任一还活着的怪物。
一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物恰在某一分钟开始时到达城市，这会被视为输掉游戏，在你可以使用武器之前，游戏就会结束。
返回在你输掉游戏前可以消灭的怪物的最大数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回 n 。

示例 1：

输入：dist = [1,3,4], speed = [1,1,1]
输出：3
解释：
第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,2,3]，你没有消灭任何怪物。
第 2 分钟开始时，怪物的距离是 [X,1,2]，你消灭了第二个怪物。
第 3 分钟开始时，怪物的距离是 [X,X,1]，你消灭了第三个怪物。
所有 3 个怪物都可以被消灭。

2. 解答分析

dist[]数组表示的距离，speed[]表示的是移动的速度（每次移动的距离），所以可见对于怪物而言，需要计算的就是移动所需的时间，或者说是次数问题
那对于人而言，每分钟我们都可以杀一只怪兽，如果怪兽在我们击杀前到达，也就是人杀死怪物需要的次数比怪物到达城市所需的次数多的话，则会输掉比赛。
所以返回的是可以杀死多少个这样的怪物，是人可以拥有的移动的次数i（人每移动一次杀死一只怪兽）

3. 具体代码

首先引入数组arr[]，用于表示每只怪兽到达需要的时间（次数）
接着遍历所有的怪兽数组dist[],补充当前的arr[]数组
接着排序，对arr[]数组进行排序，其实就是危险性的排序
遍历当前的arr[]数组，判断当前的人的移动次数和对应的的怪兽次数比较

java代码如下：

class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        //java, 排序
        int n = dist.length;
        //记录每只怪兽到达需要的时间
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            if (dist[i] == 0) return 0;//如果距离为0.此时怪兽已经到达
            arr[i] = dist[i] % speed[i] == 0 ? dist[i] / speed[i] - 1: dist[i] / speed[i];//之所以取余，是因为speed[i]每一次都是以speed[i]的速度增长，而不是单纯地走一步++，
            //如果此时的取余为0，说明还可以让它走商减1次（除去最后遇到的那次），也就是剩余商-1次机会
            //如果此时的取余不为0，说明还剩下商次机会，不用减1，是因为不会刚好遇到
        }
        //排序，对所有的arr时间进行排序
        Arrays.sort(arr);
        //每分钟我们都可以杀一只怪兽，如果怪兽在我们击杀前到达，则会输掉比赛
        for (int i = 1; i < n; i++) {//i表示次数问题
            if (arr[i] < i) return i;
        }
        return n;
    }
}

复杂度分析
- 时间复杂度: $O(nlogn)$
  1. 首先，对于遍历数组 dist 和 speed 来计算 arr 数组的时间复杂度是 O(n)，其中 n 是数组的长度。
  2. 接下来，对 arr 数组进行排序的时间复杂度是 O(nlogn)，其中 n 是数组的长度。
  3. 最后，再次遍历 arr 数组进行比较的时间复杂度是 O(n)
- 空间复杂度： $O(n)$
  
  该代码仅仅使用了一个数组的长度来存储每只怪兽会到达的时间，n为数组的长度，在这之后并未使用额外的空间了