一、题目

1、题目描述

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

示例 1：
输入：
[[1,2,3],
[4,5],
[1,2,3]]
输出： 4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

2、基础框架

C++版本给出的基础框架如下：

3、原题链接

二、解题报告

1、思路分析

$(1)$ 分别提取出所有数组的最小值和最大值得到小数组a和大数组b。
$(2)$ 在小数组a中找出最小值和次小值，以及最小值出现的次数和最小值下标。
$(3)$ 在大数组b中找出最大值和次大值，以及最大值出现的次数和最大值下标。
$(4)$ 如果最小值或者最大值不止一次，或者最小值下标与最大值下标不相同，直接返回最大值减最小值。
$(5)$ 否则返回最大值减次小值与次大值减最小值之间的最大值。

2、时间复杂度

时间复杂度O(n)

3、代码详解

class Solution {
public:int maxDistance(vector<vector<int>>& arrays) {vector<int> a;vector<int> b;for (int i = 0; i < arrays.size(); i++) {if(arrays[i].size() != 0) {a.push_back(arrays[i][0]);b.push_back(arrays[i][arrays[i].size()-1]);}}int m1 = -10001;int m1index = -1;int m2 = -10001;int l1 = 10001;int l1index = -1;int l2 = 10001;int m1cnt = 1;int l1cnt = 1;for (int i = 0; i < a.size(); i++) {if (a[i] < l1) {// l1不是第一次更新，则之前的最小值为当前次小值if (l1 != 10001) {l2 = l1;}l1index = i;l1 = a[i];// 最小值更新，最小值出现的次数也要刷新l1cnt = 1;} else if (a[i] == l1) {// 记录最小值出现次数l1cnt++;} else {// 如果当前值不是最小值，则判断当前值是否值次小值l2 = min(l2, a[i]);}if (b[i] > m1) {// m1不是第一次更新，则之前的最大值为当前次大值if (m1 != -10001) {m2 = m1;}m1index = i;m1 = b[i];m1cnt = 1;} else if (b[i] == m1) {m1cnt++;} else {// 如果当前值不是最大值，则判断当前值是否值次大值m2 = max(m2, b[i]);}}if (l1cnt > 1 || m1cnt > 1 || l1index != m1index) {return m1 - l1;} else {return max(m1-l2, m2-l1);}}
};