wordpress建外贸网站,中小型网站建设怎么样,南阳注册公司多少钱,华为云虚拟主机给定 m 个数组#xff0c;每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数#xff08;每个数组选一个#xff09;并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离
示例 1#xff1a;…给定 m 个数组每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数每个数组选一个并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离
示例 1 输入 [[1,2,3], [4,5], [1,2,3]] 输出 4 解释 一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1同时从第二个数组中选择 5 。
算法思路 遍历数组我们可以记录每个数组中的最小值和最大值以及它们在数组中的位置。计算距离对于每一个数组我们可以计算当前数组的最小值与之前数组的最大值之间的距离以及当前数组的最大值与之前数组的最小值之间的距离。更新最大距离在遍历的过程中不断更新最大距离。 #include iostream
#includealgorithm
#include vector
using namespace std;class Solution
{
public:int maxDistance(vectorvectorint 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;vectorvectorint arrays { {1, 2, 3}, {4, 5}, {1, 2, 3} };cout 最大距离是: solution.maxDistance(arrays) endl;return 0;
}题目来源LeetCode
