class Solution {
public:
int minimumDistance(vector<vector<int>>& points) {
}
};
100240. 最小化曼哈顿距离
给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。
两点之间的距离定义为它们的曼哈顿距离。
请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。
示例 1：
输入：points = [[3,10],[5,15],[10,2],[4,4]] 输出：12 解释：移除每个点后的最大距离如下所示： - 移除第 0 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间，为 |5 - 10| + |15 - 2| = 18 。 - 移除第 1 个点后，最大距离在点 (3, 10) 和 (10, 2) 之间，为 |3 - 10| + |10 - 2| = 15 。 - 移除第 2 个点后，最大距离在点 (5, 15) 和 (4, 4) 之间，为 |5 - 4| + |15 - 4| = 12 。 - 移除第 3 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间的，为 |5 - 10| + |15 - 2| = 18 。 在恰好移除一个点后，任意两点之间的最大距离可能的最小值是 12 。
示例 2：
输入：points = [[1,1],[1,1],[1,1]] 输出：0 解释：移除任一点后，任意两点之间的最大距离都是 0 。
提示：
3 <= points.length <= 105points[i].length == 21 <= points[i][0], points[i][1] <= 108原站题解
javascript 解法, 执行用时: 555 ms, 内存消耗: 89.1 MB, 提交时间: 2024-07-09 09:09:02
/**
* @param {number[][]} points
* @return {number}
*/
var minimumDistance = function(points) {
const n = points.length;
const sx = [];
const sy = [];
for (let i = 0; i < n; i++) {
const [x, y] = points[i];
sx.push([x - y, i]);
sy.push([x + y, i]);
}
sx.sort((a, b) => a[0] - b[0]);
sy.sort((a, b) => a[0] - b[0]);
const maxVal1 = sx[n - 1][0] - sx[0][0];
const maxVal2 = sy[n - 1][0] - sy[0][0];
let res = Infinity;
if (maxVal1 >= maxVal2) {
const i = sx[0][1], j = sx[n - 1][1];
// 去掉 i 后的最大曼哈顿距离
res = Math.min(res, Math.max(remove(sx, i), remove(sy, i)));
// 去掉 j 后的最大曼哈顿距离
res = Math.min(res, Math.max(remove(sx, j), remove(sy, j)));
} else {
const i = sy[0][1], j = sy[n - 1][1];
// 去掉 i 后的最大曼哈顿距离
res = Math.min(res, Math.max(remove(sx, i), remove(sy, i)));
// 去掉 j 后的最大曼哈顿距离
res = Math.min(res, Math.max(remove(sx, j), remove(sy, j)));
}
return res;
};
function remove(arr, i) {
const n = arr.length;
if (arr[0][1] === i) {
return arr[n - 1][0] - arr[1][0];
} else if (arr[n - 1][1] === i) {
return arr[n - 2][0] - arr[0][0];
} else {
return arr[n - 1][0] - arr[0][0];
}
}
rust 解法, 执行用时: 41 ms, 内存消耗: 11.3 MB, 提交时间: 2024-07-09 09:08:47
// 枚举最大值与最小值
impl Solution {
pub fn minimum_distance(points: Vec<Vec<i32>>) -> i32 {
let n = points.len();
let mut sx: Vec<(i32, usize)> = Vec::with_capacity(n);
let mut sy: Vec<(i32, usize)> = Vec::with_capacity(n);
for (i, point) in points.iter().enumerate() {
let x = point[0];
let y = point[1];
sx.push((x - y, i));
sy.push((x + y, i));
}
sx.sort_unstable_by_key(|pair| pair.0);
sy.sort_unstable_by_key(|pair| pair.0);
let max_val1 = sx[n - 1].0 - sx[0].0;
let max_val2 = sy[n - 1].0 - sy[0].0;
let mut res = std::i32::MAX;
if max_val1 >= max_val2 {
let i = sx[0].1;
let j = sx[n - 1].1;
// 去掉 i 后的最大曼哈顿距离
res = res.min(std::cmp::max(Self::remove(&sx, i), Self::remove(&sy, i)));
// 去掉 j 后的最大曼哈顿距离
res = res.min(std::cmp::max(Self::remove(&sx, j), Self::remove(&sy, j)));
} else {
let i = sy[0].1;
let j = sy[n - 1].1;
// 去掉 i 后的最大曼哈顿距离
res = res.min(std::cmp::max(Self::remove(&sx, i), Self::remove(&sy, i)));
// 去掉 j 后的最大曼哈顿距离
res = res.min(std::cmp::max(Self::remove(&sx, j), Self::remove(&sy, j)));
}
res
}
fn remove(arr: &Vec<(i32, usize)>, i: usize) -> i32 {
let n = arr.len();
if arr[0].1 == i {
return arr[n - 1].0 - arr[1].0;
} else if arr[n - 1].1 == i {
return arr[n - 2].0 - arr[0].0;
} else {
return arr[n - 1].0 - arr[0].0;
}
}
}
rust 解法, 执行用时: 200 ms, 内存消耗: 10.6 MB, 提交时间: 2024-07-09 09:08:25
// 枚举所有点
use std::collections::BTreeMap;
impl Solution {
pub fn minimum_distance(points: Vec<Vec<i32>>) -> i32 {
let mut sx: BTreeMap<i32, i32> = BTreeMap::new();
let mut sy: BTreeMap<i32, i32> = BTreeMap::new();
for p in &points {
let sx_key = p[0] - p[1];
let sy_key = p[0] + p[1];
*sx.entry(sx_key).or_insert(0) += 1;
*sy.entry(sy_key).or_insert(0) += 1;
}
let mut res = std::i32::MAX;
for p in &points {
let sx_key = p[0] - p[1];
let sy_key = p[0] + p[1];
let count_sx = sx.entry(sx_key).or_insert(0);
*count_sx -= 1;
if *count_sx == 0 {
sx.remove(&sx_key);
}
let count_sy = sy.entry(sy_key).or_insert(0);
*count_sy -= 1;
if *count_sy == 0 {
sy.remove(&sy_key);
}
if !sx.is_empty() && !sy.is_empty() {
let max_sx = *sx.iter().rev().next().unwrap().0 - *sx.iter().next().unwrap().0;
let max_sy = *sy.iter().rev().next().unwrap().0 - *sy.iter().next().unwrap().0;
res = res.min(max_sx.max(max_sy));
}
*sx.entry(sx_key).or_insert(0) += 1;
*sy.entry(sy_key).or_insert(0) += 1;
}
res
}
}
golang 解法, 执行用时: 862 ms, 内存消耗: 26.5 MB, 提交时间: 2024-03-31 21:53:20
// https://pkg.go.dev/github.com/emirpasic/gods/v2@v2.0.0-alpha
func minimumDistance(points [][]int) int {
xs := redblacktree.New[int, int]()
ys := redblacktree.New[int, int]()
for _, p := range points {
x, y := p[0]+p[1], p[1]-p[0]
put(xs, x)
put(ys, y)
}
ans := math.MaxInt
for _, p := range points {
x, y := p[0]+p[1], p[1]-p[0]
remove(xs, x)
remove(ys, y)
ans = min(ans, max(xs.Right().Key-xs.Left().Key, ys.Right().Key-ys.Left().Key))
put(xs, x)
put(ys, y)
}
return ans
}
func put(t *redblacktree.Tree[int, int], v int) {
c, _ := t.Get(v)
t.Put(v, c+1)
}
func remove(t *redblacktree.Tree[int, int], v int) {
c, _ := t.Get(v)
if c == 1 {
t.Remove(v)
} else {
t.Put(v, c-1)
}
}
golang 解法, 执行用时: 160 ms, 内存消耗: 17 MB, 提交时间: 2024-03-31 21:53:02
func minimumDistance(points [][]int) int {
const inf = math.MaxInt
maxX1, maxX2, maxY1, maxY2 := -inf, -inf, -inf, -inf
minX1, minX2, minY1, minY2 := inf, inf, inf, inf
for _, p := range points {
x := p[0] + p[1]
y := p[1] - p[0]
// x 最大次大
if x > maxX1 {
maxX2 = maxX1
maxX1 = x
} else if x > maxX2 {
maxX2 = x
}
// x 最小次小
if x < minX1 {
minX2 = minX1
minX1 = x
} else if x < minX2 {
minX2 = x
}
// y 最大次大
if y > maxY1 {
maxY2 = maxY1
maxY1 = y
} else if y > maxY2 {
maxY2 = y
}
// y 最小次小
if y < minY1 {
minY2 = minY1
minY1 = y
} else if y < minY2 {
minY2 = y
}
}
ans := inf
for _, p := range points {
x := p[0] + p[1]
y := p[1] - p[0]
dx := f(x, maxX1, maxX2) - f(x, minX1, minX2)
dy := f(y, maxY1, maxY2) - f(y, minY1, minY2)
ans = min(ans, max(dx, dy))
}
return ans
}
func f(v, v1, v2 int) int {
if v == v1 {
return v2
}
return v1
}
cpp 解法, 执行用时: 258 ms, 内存消耗: 118.2 MB, 提交时间: 2024-03-31 21:52:43
class Solution {
// 更新最大次大
void update_max(int v, int &max1, int &max2) {
if (v > max1) {
max2 = max1;
max1 = v;
} else if (v > max2) {
max2 = v;
}
}
// 更新最小次小
void update_min(int v, int &min1, int &min2) {
if (v < min1) {
min2 = min1;
min1 = v;
} else if (v < min2) {
min2 = v;
}
}
public:
int minimumDistance(vector<vector<int>> &points) {
int max_x1 = INT_MIN, max_x2 = INT_MIN, max_y1 = INT_MIN, max_y2 = INT_MIN;
int min_x1 = INT_MAX, min_x2 = INT_MAX, min_y1 = INT_MAX, min_y2 = INT_MAX;
for (auto &p : points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
update_max(x, max_x1, max_x2);
update_min(x, min_x1, min_x2);
update_max(y, max_y1, max_y2);
update_min(y, min_y1, min_y2);
}
int ans = INT_MAX;
for (auto &p : points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
int dx = (x == max_x1 ? max_x2 : max_x1) - (x == min_x1 ? min_x2 : min_x1);
int dy = (y == max_y1 ? max_y2 : max_y1) - (y == min_y1 ? min_y2 : min_y1);
ans = min(ans, max(dx, dy));
}
return ans;
}
};
cpp 解法, 执行用时: 1122 ms, 内存消耗: 220 MB, 提交时间: 2024-03-31 21:52:29
class Solution {
public:
int minimumDistance(vector<vector<int>> &points) {
multiset<int> xs, ys;
for (auto &p : points) {
xs.insert(p[0] + p[1]);
ys.insert(p[1] - p[0]);
}
int ans = INT_MAX;
for (auto &p : points) {
int x = p[0] + p[1], y = p[1] - p[0];
xs.erase(xs.find(x));
ys.erase(ys.find(y));
ans = min(ans, max(*xs.rbegin() - *xs.begin(), *ys.rbegin() - *ys.begin()));
xs.insert(x);
ys.insert(y);
}
return ans;
}
};
java 解法, 执行用时: 459 ms, 内存消耗: 94.7 MB, 提交时间: 2024-03-31 21:52:17
class Solution {
public int minimumDistance(int[][] points) {
TreeMap<Integer, Integer> xs = new TreeMap<>();
TreeMap<Integer, Integer> ys = new TreeMap<>();
for (int[] p : points) {
xs.merge(p[0] + p[1], 1, Integer::sum);
ys.merge(p[1] - p[0], 1, Integer::sum);
}
int ans = Integer.MAX_VALUE;
for (int[] p : points) {
int x = p[0] + p[1], y = p[1] - p[0];
if (xs.get(x) == 1) xs.remove(x);
else xs.merge(x, -1, Integer::sum);
if (ys.get(y) == 1) ys.remove(y);
else ys.merge(y, -1, Integer::sum);
ans = Math.min(ans, Math.max(xs.lastKey() - xs.firstKey(), ys.lastKey() - ys.firstKey()));
xs.merge(x, 1, Integer::sum);
ys.merge(y, 1, Integer::sum);
}
return ans;
}
}
java 解法, 执行用时: 3 ms, 内存消耗: 80.3 MB, 提交时间: 2024-03-31 21:52:02
class Solution {
public int minimumDistance(int[][] points) {
final int INF = Integer.MAX_VALUE;
int maxX1 = -INF, maxX2 = -INF, maxY1 = -INF, maxY2 = -INF;
int minX1 = INF, minX2 = INF, minY1 = INF, minY2 = INF;
for (int[] p : points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
// x 最大次大
if (x > maxX1) {
maxX2 = maxX1;
maxX1 = x;
} else if (x > maxX2) {
maxX2 = x;
}
// x 最小次小
if (x < minX1) {
minX2 = minX1;
minX1 = x;
} else if (x < minX2) {
minX2 = x;
}
// y 最大次大
if (y > maxY1) {
maxY2 = maxY1;
maxY1 = y;
} else if (y > maxY2) {
maxY2 = y;
}
// y 最小次小
if (y < minY1) {
minY2 = minY1;
minY1 = y;
} else if (y < minY2) {
minY2 = y;
}
}
int ans = INF;
for (int[] p : points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
int dx = (x == maxX1 ? maxX2 : maxX1) - (x == minX1 ? minX2 : minX1);
int dy = (y == maxY1 ? maxY2 : maxY1) - (y == minY1 ? minY2 : minY1);
ans = Math.min(ans, Math.max(dx, dy));
}
return ans;
}
}
python3 解法, 执行用时: 1907 ms, 内存消耗: 55.1 MB, 提交时间: 2024-03-31 21:51:32
from sortedcontainers import SortedList
class Solution:
def minimumDistance(self, points: List[List[int]]) -> int:
xs = SortedList()
ys = SortedList()
for x, y in points:
xs.add(x + y)
ys.add(y - x)
ans = inf
for x, y in points:
x, y = x + y, y - x
xs.remove(x)
ys.remove(y)
ans = min(ans, max(xs[-1] - xs[0], ys[-1] - ys[0]))
xs.add(x)
ys.add(y)
return ans
def minimumDistance2(self, points: List[List[int]]) -> int:
max_x1, max_x2 = nlargest(2, (x + y for x, y in points)) # x 最大次大
min_x1, min_x2 = nsmallest(2, (x + y for x, y in points)) # x 最小次小
max_y1, max_y2 = nlargest(2, (y - x for x, y in points)) # y 最大次大
min_y1, min_y2 = nsmallest(2, (y - x for x, y in points)) # y 最小次小
ans = inf
for x, y in points:
x, y = x + y, y - x
dx = (max_x2 if x == max_x1 else max_x1) - (min_x2 if x == min_x1 else min_x1)
dy = (max_y2 if y == max_y1 else max_y1) - (min_y2 if y == min_y1 else min_y1)
ans = min(ans, max(dx, dy))
return ans