这道题的核心思路与 Java 版本一致需要通过坐标变换将曼哈顿距离转化为切比雪夫距离然后利用有序容器动态维护最值。主要步骤1. 坐标变换将点 (x, y) 转换为 (xy, x-y)2. 关键性质原曼哈顿距离 变换后切比雪夫距离 max(|Δu|, |Δv|)3. 全局最大距离 max( (u_max - u_min), (v_max - v_min) )4. 枚举删除使用 multiset 维护所有点的 u 和 v每次删除一个点计算当前最大距离取最小值cpp#include vector#include set#include algorithm#include climitsusing namespace std;class Solution {public:int minimumDistance(vectorvectorint points) {multisetint sums; // 存储所有 xymultisetint diffs; // 存储所有 x-y// 初始化所有点的变换坐标for (const auto p : points) {sums.insert(p[0] p[1]);diffs.insert(p[0] - p[1]);}int ans INT_MAX;// 尝试移除每一个点for (const auto p : points) {int sum p[0] p[1];int diff p[0] - p[1];// 移除当前点sums.erase(sums.find(sum));diffs.erase(diffs.find(diff));// 计算剩余点的最大曼哈顿距离int currentMax max(*sums.rbegin() - *sums.begin(), // u 的范围*diffs.rbegin() - *diffs.begin() // v 的范围);ans min(ans, currentMax);// 恢复当前点用于下一轮枚举sums.insert(sum);diffs.insert(diff);}return ans;}};复杂度分析· 时间复杂度O(n log n)其中 n 是点的数量。遍历每个点 O(n)每次插入删除 O(log n)· 空间复杂度O(n)用于存储两个 multiset注意· 使用 multiset 而非 set因为可能存在重复坐标· 删除时要使用 find() 获取迭代器避免删除所有相同值的元素· 使用 rbegin() 获取最大值begin() 获取最小值
DeepSeek LeetCode 3102. 最小化曼哈顿距离 C++实现
发布时间：2026/6/10 9:37:10
这道题的核心思路与 Java 版本一致需要通过坐标变换将曼哈顿距离转化为切比雪夫距离然后利用有序容器动态维护最值。主要步骤1. 坐标变换将点 (x, y) 转换为 (xy, x-y)2. 关键性质原曼哈顿距离 变换后切比雪夫距离 max(|Δu|, |Δv|)3. 全局最大距离 max( (u_max - u_min), (v_max - v_min) )4. 枚举删除使用 multiset 维护所有点的 u 和 v每次删除一个点计算当前最大距离取最小值cpp#include vector#include set#include algorithm#include climitsusing namespace std;class Solution {public:int minimumDistance(vectorvectorint points) {multisetint sums; // 存储所有 xymultisetint diffs; // 存储所有 x-y// 初始化所有点的变换坐标for (const auto p : points) {sums.insert(p[0] p[1]);diffs.insert(p[0] - p[1]);}int ans INT_MAX;// 尝试移除每一个点for (const auto p : points) {int sum p[0] p[1];int diff p[0] - p[1];// 移除当前点sums.erase(sums.find(sum));diffs.erase(diffs.find(diff));// 计算剩余点的最大曼哈顿距离int currentMax max(*sums.rbegin() - *sums.begin(), // u 的范围*diffs.rbegin() - *diffs.begin() // v 的范围);ans min(ans, currentMax);// 恢复当前点用于下一轮枚举sums.insert(sum);diffs.insert(diff);}return ans;}};复杂度分析· 时间复杂度O(n log n)其中 n 是点的数量。遍历每个点 O(n)每次插入删除 O(log n)· 空间复杂度O(n)用于存储两个 multiset注意· 使用 multiset 而非 set因为可能存在重复坐标· 删除时要使用 find() 获取迭代器避免删除所有相同值的元素· 使用 rbegin() 获取最大值begin() 获取最小值
)
