Medium

题目描述

给你一个二维整数数组 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。

示例 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 <= 10^5
  • towers[i] = [xi, yi, qi]
  • center = [cx, cy]
  • 0 <= xi, yi, qi, cx, cy <= 10^5
  • 0 <= radius <= 10^5

解题思路

这道题需要找到在指定半径范围内质量因子最大的塔台，如果质量相同则选择字典序最小的坐标。

解题思路：

  1. 遍历筛选：遍历所有塔台，计算每个塔台到中心点的曼哈顿距离，筛选出所有可达的塔台（距离 ≤ radius）。

  2. 维护最优解：在遍历过程中，维护当前找到的最优塔台。对于每个可达塔台，需要与当前最优解比较：

    • 如果质量因子更大，更新最优解
    • 如果质量因子相等但坐标字典序更小，也更新最优解

  3. 字典序比较：坐标 [x1, y1] 字典序小于 [x2, y2] 当且仅当 x1 < x2，或者 x1 == x2 且 y1 < y2。

  4. 边界处理：如果没有找到任何可达塔台，返回 [-1, -1]。

算法步骤：

  • 初始化结果为 [-1, -1]，最大质量为 -1
  • 遍历每个塔台，计算曼哈顿距离
  • 对于可达塔台，检查是否应该更新最优解
  • 更新条件：质量更大，或质量相等但字典序更小

代码实现

class Solution {
public:
    vector<int> bestTower(vector<vector<int>>& towers, vector<int>& center, int radius) {
        vector<int> result = {-1, -1};
        int maxQuality = -1;
        int cx = center[0], cy = center[1];
        
        for (auto& tower : towers) {
            int x = tower[0], y = tower[1], q = tower[2];
            int distance = abs(x - cx) + abs(y - cy);
            
            if (distance <= radius) {
                if (q > maxQuality || 
                    (q == maxQuality && (x < result[0] || (x == result[0] && y < result[1])))) {
                    result = {x, y};
                    maxQuality = q;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def bestTower(self, towers: List[List[int]], center: List[int], radius: int) -> List[int]:
        result = [-1, -1]
        max_quality = -1
        cx, cy = center
        
        for x, y, q in towers:
            distance = abs(x - cx) + abs(y - cy)
            
            if distance <= radius:
                if (q > max_quality or 
                    (q == max_quality and (x < result[0] or (x == result[0] and y < result[1])))):
                    result = [x, y]
                    max_quality = q
        
        return result

public class Solution {
    public int[] BestTower(int[][] towers, int[] center, int radius) {
        int[] result = {-1, -1};
        int maxQuality = -1;
        int cx = center[0], cy = center[1];
        
        foreach (int[] tower in towers) {
            int x = tower[0], y = tower[1], q = tower[2];
            int distance = Math.Abs(x - cx) + Math.Abs(y - cy);
            
            if (distance <= radius) {
                if (q > maxQuality || 
                    (q == maxQuality && (x < result[0] || (x == result[0] && y < result[1])))) {
                    result[0] = x;
                    result[1] = y;
                    maxQuality = q;
                }
            }
        }
        
        return result;
    }
}

var bestTower = function(towers, center, radius) {
    let bestQuality = -1;
    let bestCoord = [-1, -1];
    
    for (let tower of towers) {
        let [x, y, q] = tower;
        let distance = Math.abs(x - center[0]) + Math.abs(y - center[1]);
        
        if (distance <= radius) {
            if (q > bestQuality || (q === bestQuality && (x < bestCoord[0] || (x === bestCoord[0] && y < bestCoord[1])))) {
                bestQuality = q;
                bestCoord = [x, y];
            }
        }
    }
    
    return bestCoord;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是塔台数量。算法只需要遍历一次所有塔台，每次操作都是常数时间，因此时间复杂度为 O(n)。空间复杂度为 O(1)，因为只使用了常数额外空间。