LeetCode Maximum Distance in Arrays 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. Example 1:

Input:
[[1,2,3],
 [4,5],
 [1,2,3]]
Output: 4
Explanation:
One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Note:

1. Each given array will have at least 1 number. There will be at least two non-empty arrays.
2. The total number of the integers in all the m arrays will be in the range of [2, 10000].
3. The integers in the m arrays will be in the range of [-10000, 10000].

---

给定m个已从小到大排序的数组，要求从两个不同的数组中取出两个数，使得这两个数的差的绝对值最大，问最大的差的绝对值是多少。 因为数组已排序，所以最大的差值肯定等于某个数组的最大值和另一个数组的最小值的差。这里唯一需要注意的是两个数必须选自两个不同的数组。 我开始的做法是这样的，把所有数组的最大值和最小值都拿出来，然后重新排个序。在新数组中，如果最大值和最小值来自不同的数组，则他们的差就是最终结果。加入最大值和最小值是来自同一个数组的，则求最大值和次小值的差以及次大值和最小值的差中的最大值。因为最大值和最小值来自同一个数组，所以最大值和次小值以及次大值和最小值肯定不是来自同一个数组的。 代码如下： [cpp] class Solution { struct P { int idx; int value; P(int i, int v) :idx(i), value(v) {}; bool operator<(const P& p) { return this->value < p.value; } }; public: int maxDistance(vector<vector<int>>& arrays) { vector<P> vp; for (int i = 0; i < arrays.size(); ++i) { vp.push_back({ i,arrays[i][0] }); vp.push_back({ i,arrays[i][arrays[i].size() – 1] }); } sort(vp.begin(), vp.end()); int ans = 0, n = vp.size(); if (vp[0].idx != vp[n – 1].idx)return abs(vp[n – 1].value – vp[0].value); return max(abs(vp[n – 1].value – vp[1].value), abs(vp[n – 2].value – vp[0].value)); } }; [/cpp] 本代码提交AC，用时26MS。因为要对m个数组的最大值和最小值排序，所以时间复杂度为O((2m)lg(2m))。 讨论区还有一种解法，只需要O(m)的复杂度。我们遍历每个数组，记录之前所有数组的最小值的最小值以及最大值的最大值，然后用当前数组的最大值和最小值减去之前所有数组中的最小值的最小值以及最大值的最大值，求绝对值，更新结果。这样就作差的两个数肯定来自不同的数组，避免了之前的问题。 代码如下： [cpp] class Solution { public: int maxDistance(vector<vector<int>>& arrays) { int ans = INT_MIN; int curMin = arrays[0][0], curMax = arrays[0][arrays[0].size() – 1]; for(int i = 1; i < arrays.size(); ++i) { ans = max(ans, abs(arrays[i][0] – curMax)); ans = max(ans, abs(arrays[i][arrays[i].size() – 1] – curMin)); curMin = min(curMin, arrays[i][0]); curMax = max(curMax, arrays[i][arrays[i].size() – 1]); } return ans; } }; [/cpp] 本代码提交AC，用时22MS。]]>