2026-05-20：最好可到达的塔。用go语言，给定一个二维整数数组 towers，其中每个元素 towers[i] = [x_i, y_i, q_i...|spiderlinebreak|复杂度|整数|遍历

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++完整代码如下：

  

  

  


 using namespace std;

 vector bestTower(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; 
 
 
             }  
 else 
 if 
  (q == maxQ) { 
 
 
                  
 if 
  (x < minX) { 
 
 
                     minX = x; 
 
 
                     minY = y; 
 
 
                 }  
 else 
 if 
  (x == minX && y < minY) { 
 
 
                     minY = y; 
 
 
                 } 
 
 
             } 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  {minX, minY}; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     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; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 }