当前位置：首页 > news >正文

数组列表中的最大距离

news 2025/7/17 2:35:34

给定 m 个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离

示例 1：

输入： [[1,2,3], [4,5], [1,2,3]]
输出： 4

解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

算法思路

遍历数组：我们可以记录每个数组中的最小值和最大值，以及它们在数组中的位置。
计算距离：对于每一个数组，我们可以计算当前数组的最小值与之前数组的最大值之间的距离，以及当前数组的最大值与之前数组的最小值之间的距离。
更新最大距离：在遍历的过程中，不断更新最大距离。

#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;class Solution
{
public:int maxDistance(vector<vector<int>>& arrays){// 获取第一个数组的最大值与最小值int minVal = arrays[0][0];int maxVal = arrays[0].back();// 循环遍历更新最大值与最小值int maxDist = 0;for (int i = 1; i < arrays.size(); i++){// 计算当前最大值与之前最小值的距离并更新距离maxDist = max(maxDist, abs(arrays[i].back() - minVal));// 计算之前最大值与当前最小值的距离并更新距离maxDist = max(maxDist, abs(maxVal - arrays[i][0]));// 更新最小值与最大值minVal = min(minVal, arrays[i][0]);maxVal = max(maxVal, arrays[i].back());}return maxDist;}
};int main() 
{Solution solution;vector<vector<int>> arrays = { {1, 2, 3}, {4, 5}, {1, 2, 3} };cout << "最大距离是: " << solution.maxDistance(arrays) << endl;return 0;
}