数组列表中的最大距离
给定 m 个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离
目标
题意中的绝对值 |a-b|等价于选取两个数组的最大、最小值相减；由于每个数组已经排序，进一步等价于\(\max(vec[i][n-1] - vec[j][0], vec[j][m-1] - vec[i][0])\)。
直观想法
找 \(\min(vec[i][0])\)和\(\max(vec[i][n-1])\)，但是还需要保障这两个数不在同一个数组中，由此产生思路：
- 依照 vec[i][0] 的值从小到大进行排序（不直接排序原数组，而是新申请 index 数组进行排序），得到 \(index_1\)
- 依照 vec[i][n-1] 的值从大到小进行排序 （不直接排序原数组，而是新申请 index 数组进行排序)，得到 \(index_2\)
- 比较两个 index 数组的第一个值是否相等，不相等则说明不是同一个数组，可直接计算得出结果；相等则还需要拿出两个index数组的第二个值进行计算比较得出结果
最优解思路
1. 仅仅两个数组a, b
很好解决——选择 \(a_{max} - b_{min}\) 和 \(b_{max} - a_{min}\) 的最大值
2. 三个数组 a, b, c
通过步骤1，可以得到一个潜在结果 ans；对于 c 的加入，选择 $ \max(a_{max}, b_{max}) - c_{min}$ 和 $c_{max} - \min(a_{min}, b_{min}) $ 的最大值
3. 进一步范化
已知 m-1 个数组的答案，而且知道真个数组的最大、最小值，先加入一个新的数组，计算得到答案。由此可以得到时间复杂度为\(O(n)\)，空间复杂度为\(O(1)\)的方法
标签：index,624,max,min,列表,vec,数组,排序,leetcode From： https://www.cnblogs.com/wyzwsy/p/18227472