LC.P1921[消灭怪物的最大数量]

方法一：贪心+排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        int n = dist.length;
        int[] times = new int[n];
        for (int i = 0; i < n; ++i) times[i] = (dist[i] - 1) / speed[i];
        Arrays.sort(times);
        for (int i = 0; i < n; ++i) {
            if (times[i] < i) {
                return i;
            }
        }
        return n;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$