Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.
给m个已经排序好的数组,从两个数组中分别挑选一个数字,使得差最大,求最大的差
Example 1:
Input:
[[1,2,3],
[4,5],
[1,2,3]]
Output: 4
Explanation:
从[1,2,3]中取1,[4,5]中取5。最大差为5-1=4
最小值来源于每个数组中下标为0的元素
最大值来源于每个数组中下标为len-1的元素
注意:不能单纯找最大最小值,因为可能来自同一数组。
int maxDistance(vector<>>& arrays) { int maxV = arrays[0][arrays[0].size() - 1]; int minV = arrays[0][0]; int diff = INT_MIN; for (int i = 1; i < arrays.size(); i++) { diff = diff < maxV - arrays[i][0] ? maxV - arrays[i][0] : diff; diff = diff < arrays[i][arrays[i].size() - 1] - minV ? arrays[i][arrays[i].size() - 1] - minV : diff; maxV = maxV < arrays[i][arrays[i].size() - 1] ? arrays[i][arrays[i].size() - 1] : maxV; minV = minV > arrays[i][0] ? arrays[i][0] : minV; } return diff; }