跳转至

3809. 最好可到达的塔

题目描述

给你一个二维整数数组 towers，其中 towers[i] = [xi, yi, qi] 表示第 i 座塔的坐标 (xi, yi) 和质量因子 qi。

另外给你一个整数数组 center = [cx, cy] 表示你的位置，以及一个整数 radius。

如果一座塔与 center 之间的 曼哈顿距离小于或等于 radius，则称该塔是 可到达的。

在所有可到达的塔中：

  • 返回质量因子 最大 的塔的坐标。
  • 如果存在并列的塔，返回坐标 字典序最小 的塔。如果没有塔是可到达的，返回 [-1, -1]。

两点 (xi, yi) 和 (xj, yj) 之间的 曼哈顿距离 为 |xi - xj| + |yi - yj|。

坐标 [xi, yi] 字典序小于 [xj, yj] 是指：xi < xj，或者 xi == xj 且 yi < yj。

|x| 表示 x 的 绝对值。

 

示例 1：

输入： towers = [[1,2,5], [2,1,7], [3,1,9]], center = [1,1], radius = 2

输出： [3,1]

解释：

  • 塔 [1, 2, 5]：曼哈顿距离 = |1 - 1| + |2 - 1| = 1，可到达。
  • 塔 [2, 1, 7]：曼哈顿距离 = |2 - 1| + |1 - 1| = 1，可到达。
  • 塔 [3, 1, 9]：曼哈顿距离 = |3 - 1| + |1 - 1| = 2，可到达。

所有塔都是可到达的。最大质量因子为 9，对应塔 [3, 1]。

示例 2：

输入： towers = [[1,3,4], [2,2,4], [4,4,7]], center = [0,0], radius = 5

输出： [1,3]

解释：

  • 塔 [1, 3, 4]：曼哈顿距离 = |1 - 0| + |3 - 0| = 4，可到达。
  • 塔 [2, 2, 4]：曼哈顿距离 = |2 - 0| + |2 - 0| = 4，可到达。
  • 塔 [4, 4, 7]：曼哈顿距离 = |4 - 0| + |4 - 0| = 8，不可到达。

在可到达的塔中，最大质量因子为 4。[1, 3] 和 [2, 2] 的质量因子相同，因此返回字典序较小的坐标 [1, 3]。

示例 3：

输入： towers = [[5,6,8], [0,3,5]], center = [1,2], radius = 1

输出： [-1,-1]

解释：

  • 塔 [5, 6, 8]：曼哈顿距离 = |5 - 1| + |6 - 2| = 8，不可到达。
  • 塔 [0, 3, 5]：曼哈顿距离 = |0 - 1| + |3 - 2| = 2，不可到达。

在给定半径内没有可到达的塔，故返回 [-1, -1]。

 

提示：

  • 1 <= towers.length <= 105
  • towers[i] = [xi, yi, qi]
  • center = [cx, cy]
  • 0 <= xi, yi, qi, cx, cy <= 105
  • 0 <= radius <= 105

解法

方法一：一次遍历

我们定义一个变量 \(\textit{idx}\) 来记录当前最佳塔的下标，初始时 \(\textit{idx} = -1\)。然后我们遍历每一座塔，计算其与 \(\textit{center}\) 之间的曼哈顿距离 \(\textit{dist}\)：

\[ \textit{dist} = |x_i - cx| + |y_i - cy| \]

如果 \(\textit{dist} > \textit{radius}\)，则该塔不可到达，跳过该塔。否则，我们比较当前塔与最佳塔的质量因子 \(q\)：

  • 如果 \(\textit{idx} = -1\)，说明当前还没有可到达的塔，我们将 \(\textit{idx}\) 更新为当前塔的下标。
  • 如果当前塔的质量因子 \(q_i\) 大于最佳塔的质量因子 \(q_{\textit{idx}}\)，则将 \(\textit{idx}\) 更新为当前塔的下标。
  • 如果当前塔的质量因子 \(q_i\) 等于最佳塔的质量因子 \(q_{\textit{idx}}\)，则比较两座塔的坐标，选择字典序较小的塔。

遍历结束后，如果 \(\textit{idx} = -1\)，说明没有可到达的塔，返回 \([-1, -1]\)。否则，返回最佳塔的坐标。

时间复杂度 \(O(n)\)，其中 \(n\) 是塔的数量。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def bestTower(
        self, towers: List[List[int]], center: List[int], radius: int
    ) -> List[int]:
        cx, cy = center
        idx = -1
        for i, (x, y, q) in enumerate(towers):
            dist = abs(x - cx) + abs(y - cy)
            if dist > radius:
                continue
            if (
                idx == -1
                or towers[idx][2] < q
                or (towers[idx][2] == q and towers[i][:2] < towers[idx][:2])
            ):
                idx = i
        return [-1, -1] if idx == -1 else towers[idx][:2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] bestTower(int[][] towers, int[] center, int radius) {
        int cx = center[0], cy = center[1];
        int idx = -1;
        for (int i = 0; i < towers.length; i++) {
            int x = towers[i][0], y = towers[i][1], q = towers[i][2];
            int dist = Math.abs(x - cx) + Math.abs(y - cy);
            if (dist > radius) {
                continue;
            }
            if (idx == -1 || towers[idx][2] < q
                || (towers[idx][2] == q
                    && (x < towers[idx][0] || (x == towers[idx][0] && y < towers[idx][1])))) {
                idx = i;
            }
        }
        return idx == -1 ? new int[] {-1, -1} : new int[] {towers[idx][0], towers[idx][1]};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> bestTower(vector<vector<int>>& towers, vector<int>& center, int radius) {
        int cx = center[0], cy = center[1];
        int idx = -1;
        for (int i = 0; i < towers.size(); ++i) {
            int x = towers[i][0], y = towers[i][1], q = towers[i][2];
            int dist = abs(x - cx) + abs(y - cy);
            if (dist > radius) {
                continue;
            }
            if (
                idx == -1
                || towers[idx][2] < q
                || (towers[idx][2] == q && (x < towers[idx][0] || (x == towers[idx][0] && y < towers[idx][1])))) {
                idx = i;
            }
        }
        if (idx == -1) {
            return {-1, -1};
        }
        return {towers[idx][0], towers[idx][1]};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func bestTower(towers [][]int, center []int, radius int) []int {
    cx, cy := center[0], center[1]
    idx := -1
    for i, a := range towers {
        x, y, q := a[0], a[1], a[2]
        dist := abs(x-cx) + abs(y-cy)
        if dist > radius {
            continue
        }
        if idx == -1 ||
            towers[idx][2] < q ||
            (towers[idx][2] == q &&
                (x < towers[idx][0] ||
                    (x == towers[idx][0] && y < towers[idx][1]))) {
            idx = i
        }
    }
    if idx == -1 {
        return []int{-1, -1}
    }
    return []int{towers[idx][0], towers[idx][1]}
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function bestTower(towers: number[][], center: number[], radius: number): number[] {
    const [cx, cy] = center;
    let idx = -1;
    for (let i = 0; i < towers.length; i++) {
        const [x, y, q] = towers[i];
        const dist = Math.abs(x - cx) + Math.abs(y - cy);
        if (dist > radius) {
            continue;
        }
        if (
            idx === -1 ||
            towers[idx][2] < q ||
            (towers[idx][2] === q &&
                (x < towers[idx][0] || (x === towers[idx][0] && y < towers[idx][1])))
        ) {
            idx = i;
        }
    }
    return idx === -1 ? [-1, -1] : [towers[idx][0], towers[idx][1]];
}

评论