3809. Best Reachable Tower

📘 題目敘述

給定一個二維整數陣列 towers，其中 towers[i] = [xi, yi, qi] 表示第 i 座塔的座標 (xi, yi) 與品質值 qi。

同時給定一個整數陣列 center = [cx, cy] 表示你所在的位置，以及一個整數 radius。

若某座塔與 center 的 曼哈頓距離（Manhattan distance） 小於或等於 radius，則該塔視為 可到達（reachable）。

在所有可到達的塔之中：

• 回傳 品質值 qi 最大 的那座塔的座標
• 若品質值相同，回傳 字典序（lexicographically）較小 的座標
• 若沒有任何塔可到達，回傳 [-1, -1]

曼哈頓距離定義為： |xi - xj| + |yi - yj|

字典序比較定義為： [xi, yi] 比 [xj, yj] 小，若：

• xi < xj，或
• xi == xj 且 yi < yj

條件限制

• 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

🧠 解題思路

我的想法其實很直接：

把每一座 tower 都檢查一次，只要在範圍內，就和目前最佳答案比較。

這題沒有要最佳化到什麼資料結構或排序，因為每一座塔是否可到達，彼此之間是獨立的。

所以整體邏輯就是：

1. 逐一檢查每一座 tower 是否在 radius 範圍內
2. 若可到達：
   • 比較品質值 q 是否更大
   • 若品質相同，再比座標的字典序
3. 全部檢查完後：
   • 若有找到任何可到達的 tower，回傳最佳座標
   • 否則回傳 [-1, -1]

所有變數

• towers：所有塔的資料，每筆為 [x, y, q]
• center：中心點座標 [cx, cy]
• radius：可到達的最大曼哈頓距離
• n：tower 的總數
• q：目前找到的「最大品質值」
• xi, yi：目前最佳 tower 的座標
• check：是否至少找到一座可到達的 tower

🪜 主要流程步驟

第一步：檢查是否可到達

對每一座 towers[i]：

計算其與 center 的曼哈頓距離：

|towers[i][0] - center[0]| + |towers[i][1] - center[1]|

• 若距離 <= radius，代表這座塔可到達
• 一旦有可到達的 tower，就把 check 設為 true

第二步：更新目前最佳答案

若 tower 可到達，會分成兩種情況：

情況一：品質值更大

• 若 towers[i][2] > q
• 代表找到更好的 tower
• 直接更新：
  • q
  • xi
  • yi

情況二：品質值相同（需要 tie-breaking）

• 若 towers[i][2] == q
• 比較座標字典序：
  • x 較小者優先
  • 若 x 相同，y 較小者優先
• 若新的 tower 字典序較小，就更新座標

第三步：回傳結果

• 若 check == true → 至少有一座可到達的 tower，回傳 [xi, yi]
• 若 check == false → 沒有任何 tower 在範圍內，回傳 [-1, -1]

💡 整體邏輯總結

• 正確使用 曼哈頓距離
• 在掃描過程中即時維護「目前最佳答案」
• 清楚處理 品質值相同時的 tie-breaking 規則

時間複雜度為 O(n)，空間複雜度為 O(1)（只使用固定變數）。

💻 程式碼實作

class Solution {
public:
    vector<int> bestTower(vector<vector<int>>& towers, vector<int>& center,
                          int radius) {
        int xi = 100000, yi = 100000, q = -1;
        int n = towers.size();
        bool check = false;
        for (int i = 0; i < n; i++) {
            if (abs(towers[i][0] - center[0]) +
                abs(towers[i][1] - center[1]) <= radius) {
                check = true;
                if (towers[i][2] == q) {
                    if (towers[i][0] < xi ||
                        (towers[i][0] == xi && towers[i][1] < yi)) {
                        xi = towers[i][0];
                        yi = towers[i][1];
                    }
                } else if (towers[i][2] > q) {
                    q = towers[i][2];
                    xi = towers[i][0];
                    yi = towers[i][1];
                }
            }
        }
        if (check) {
            return {xi, yi};
        } else {
            return {-1, -1};
        }
    }
};

🔗 題目連結

https://leetcode.com/problems/best-reachable-tower/