2026-05-20：最好可到达的塔。用go语言，给定一个二维整数数组 towers，其中每个元素 towers[i] = [x_i, y_i, q_i] 表示第 i 座塔的坐标

福大大架构师每日一题

发布于 2026-05-20 13:41:54

850

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-05-20：最好可到达的塔。用go语言，给定一个二维整数数组 towers，其中每个元素 towers[i] = [x_i, y_i, q_i] 表示第 i 座塔的坐标与质量因子。

再给定一个整数数组 center = [c_x, c_y] 表示你的所在位置，以及一个整数 radius。

判断规则：当某座塔与 center 的曼哈顿距离满足

|x_i - c_x| + |y_i - c_y| <= radius

时，这座塔被认为是“可到达”。

目标：在所有可到达的塔里，选择：

1.质量因子 q_i 最大的塔；

2.如果有多个塔的 q_i 相同，则在它们中选择坐标按字典序最小的那一个（先比较 x，x 更小者更优；若 x 相同，再比较 y，y 更小者更优）。

如果没有任何塔可到达，则返回 [-1, -1]；否则返回该选中塔的坐标 [x_i, y_i]。

1 <= towers.length <= 100000。

towers[i] = [xi, yi, qi]。

center = [cx, cy]。

0 <= xi, yi, qi, cx, cy <= 100000。

0 <= radius <= 100000。

输入： 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]。

题目来自力扣3809。

一、程序整体执行步骤

步骤1：程序启动，进入主函数 main

程序从 main 函数开始运行，首先准备好题目给出的所有输入数据：

1. 塔数组 towers：存储了 3 座塔的信息
- • 第 1 座塔：坐标 (1,2)，质量因子 5
- • 第 2 座塔：坐标 (2,1)，质量因子 7
- • 第 3 座塔：坐标 (3,1)，质量因子 9
2. 中心位置 center：你的位置坐标 (1,1)
3. 半径 radius：可到达的最大曼哈顿距离 2

步骤2：调用核心函数 bestTower，开始筛选最优塔

程序把所有输入数据传入 bestTower 函数，正式开始计算。

子步骤 2.1：初始化筛选变量（设置初始状态）

函数一开始会创建 3 个关键变量，用来记录当前最优塔的信息：

1. maxQ：记录当前找到的最大质量因子，初始值设为 -1（因为质量因子最小是 0，-1 代表还没找到任何可到达塔）
2. minX：记录最优塔的 x 坐标，初始 -1
3. minY：记录最优塔的 y 坐标，初始 -1

这三个变量会在遍历过程中不断更新，最终保存最优塔的信息。

子步骤 2.2：遍历每一座塔，逐个判断是否符合条件

函数会依次检查每一座塔，对每一座塔执行以下判断流程：

检查第 1 座塔：(1,2,5)

1. 计算曼哈顿距离：|1-1| + |2-1| = 0 + 1 = 1
2. 判断是否可到达：1 ≤ 2 → 可到达
3. 对比当前最优：
- • 当前最大质量因子是 -1，5 更大
- • 因此更新最优记录：maxQ=5，minX=1，minY=2

检查第 2 座塔：(2,1,7)

1. 计算曼哈顿距离：|2-1| + |1-1| = 1 + 0 = 1
2. 判断是否可到达：1 ≤ 2 → 可到达
3. 对比当前最优：
- • 当前最大质量因子是 5，7 更大
- • 因此更新最优记录：maxQ=7，minX=2，minY=1

检查第 3 座塔：(3,1,9)

1. 计算曼哈顿距离：|3-1| + |1-1| = 2 + 0 = 2
2. 判断是否可到达：2 ≤ 2 → 可到达
3. 对比当前最优：
- • 当前最大质量因子是 7，9 更大
- • 因此更新最优记录：maxQ=9，minX=3，minY=1

子步骤 2.3：遍历完成，返回结果

所有塔检查完毕后：

• maxQ = 9（不是 -1，说明找到可到达塔）
• 最优坐标是 (3,1) 函数直接返回 [3, 1]

步骤3：主函数接收结果并打印

main 函数拿到结果 [3,1]，输出到控制台，程序结束。

二、关键筛选规则（严格按题目要求）

遍历每一座可到达塔时，只有满足以下任一条件，才会更新最优塔：

1. 当前塔的质量因子＞记录的最大质量因子
2. 质量因子相等，且：
- • 当前塔 x 坐标＜记录的 x 坐标
- • 或者 x 相等，当前塔 y 坐标＜记录的 y 坐标

如果没有任何塔可到达，最终返回 [-1, -1]。

三、时间复杂度 & 额外空间复杂度

1. 时间复杂度

• 程序只做了一次完整遍历，逐个检查每一座塔
• 遍历次数 = 塔的数量 n
• 每一次遍历内部只做：计算距离、判断、赋值，都是常数时间 O(1)
• 总时间复杂度：O(n)
- • n 是 towers 数组的长度（塔的数量）
- • 即使 n 达到 10 万，这个算法也能高效运行

2. 额外空间复杂度

• 程序只创建了固定数量的变量：cx、cy、maxQ、minX、minY、循环临时变量等
• 这些变量的数量不随塔的数量 n 变化
• 没有使用动态数组、哈希表等随输入变大的数据结构
• 总额外空间复杂度：O(1)（常数级空间）

总结

1. 执行过程：初始化 → 遍历每座塔 → 计算曼哈顿距离 → 按规则更新最优塔 → 返回结果
2. 时间复杂度：O(n)（线性遍历）
3. 额外空间复杂度：O(1)（仅使用固定变量）

Go完整代码如下：

package main

import (
    "fmt"
)

func bestTower(towers [][]int, center []int, radius int) []int {
    cx, cy := center[0], center[1]
    maxQ, minX, minY := -1, -1, -1
    for _, t := range towers {
        x, y, q := t[0], t[1], t[2]
        if abs(x-cx)+abs(y-cy) <= radius &&
            (q > maxQ || q == maxQ && (x < minX || x == minX && y < minY)) {
            maxQ, minX, minY = q, x, y
        }
    }
    return []int{minX, minY}
}

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

func main() {
    towers := [][]int{{1, 2, 5}, {2, 1, 7}, {3, 1, 9}}
    center := []int{1, 1}
    radius := 2
    result := bestTower(towers, center, radius)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def best_tower(towers, center, radius):
    cx, cy = center[0], center[1]
    max_q, min_x, min_y = -1, -1, -1
    
    for x, y, q in towers:
        if abs(x - cx) + abs(y - cy) <= radius:
            if (q > max_q or 
                q == max_q and (x < min_x or (x == min_x and y < min_y))):
                max_q, min_x, min_y = q, x, y
    
    return [min_x, min_y]


def main():
    towers = [[1, 2, 5], [2, 1, 7], [3, 1, 9]]
    center = [1, 1]
    radius = 2
    result = best_tower(towers, center, radius)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> bestTower(vector<vector<int>>& towers, vector<int>& center, int radius) {
    int cx = center[0];
    int cy = center[1];
    int maxQ = -1;
    int minX = -1;
    int minY = -1;

    for (const auto& tower : towers) {
        int x = tower[0];
        int y = tower[1];
        int q = tower[2];

        int manhattanDistance = abs(x - cx) + abs(y - cy);

        if (manhattanDistance <= radius) {
            if (q > maxQ) {
                maxQ = q;
                minX = x;
                minY = y;
            } elseif (q == maxQ) {
                if (x < minX) {
                    minX = x;
                    minY = y;
                } elseif (x == minX && y < minY) {
                    minY = y;
                }
            }
        }
    }

    return {minX, minY};
}

int main() {
    vector<vector<int>> towers = {{1, 2, 5}, {2, 1, 7}, {3, 1, 9}};
    vector<int> center = {1, 1};
    int radius = 2;

    vector<int> result = bestTower(towers, center, radius);

    cout << "[" << result[0] << ", " << result[1] << "]" << endl;

    return0;
}