小红的数组

题目分析

题目要求对平面上的 $n$ 个点，对于每个点，计算出与它曼哈顿距离最远的点的距离。
曼哈顿距离定义为：
$dist(a_i, a_j) = |x_i - x_j|$ $+ |y_i - y_j|$

当数据量较大 $(n≤2\times10^5)$ 时，直接暴力 $O(n^2)$ 显然会超时，因此需要优化。

小红拿到一个长度为 $n$ 的数组 $a$

第 $i$ 个元素为 $(x_i,y_i)$ ，编号为 $i$ 。