LeetCode 624. 数组列表中的最大距离

文章目录

1. 题目2. 解题2.1 暴力超时2.2 优化

1. 题目

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

示例 1： 输入： [[1,2,3], [4,5], [1,2,3]] 输出： 4 解释： 一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1， 同时从第二个数组中选择 5 。 注意： 每个给定数组至少会有 1 个数字。列表中至少有两个非空数组。 所有 m 个数组中的数字总数目在范围 [2, 10000] 内。 m 个数组中所有整数的范围在 [-10000, 10000] 内。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-distance-in-arrays 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 暴力超时

120 / 124 个通过测试用例

class Solution { public: int maxDistance(vector<vector<int>>& arrays) { int i, j, maxdis = 0, n = arrays.size(); for(i = 0; i < n; ++i) { for(j = i+1; j < n; ++j) { maxdis = max(maxdis, abs(arrays[i].front()-arrays[j].back())); maxdis = max(maxdis, abs(arrays[j].front()-arrays[i].back())); } } return maxdis; } };

2.2 优化

判断过了的数组，可以进行合并，只有合并以后的 最大的值，最小的值 起作用 class Solution { public: int maxDistance(vector<vector<int>>& arrays) { int i, j, maxdis = 0, n = arrays.size(); int MAX = arrays[0].back(), MIN = arrays[0].front(); for(i = 1; i < n; ++i) { maxdis = max(maxdis, abs(arrays[i].front()-MAX)); maxdis = max(maxdis, abs(arrays[i].back()-MIN)); MIN = min(MIN, arrays[i].front()); MAX = max(MAX, arrays[i].back()); } return maxdis; } };

56 ms 16.5 MB

---

长按或扫码关注我的公众号，一起加油、一起学习进步！