力扣leetCode: 624 数组列表中的最大距离

题目：

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

返回最大距离。

示例 1：

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

示例 2：

输入：arrays = [[1],[1]]
输出：0

提示：

m == arrays.length
2 <= m <= 10^5
1 <= arrays[i].length <= 500
-10^4 <= arrays[i][j] <= 10^4
arrays[i] 以升序排序。
所有数组中最多有 10^5 个整数。

解法：遍历找出最大值和最小值

初始代码

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int min = 10001;
        int max = -10001;
        for(auto i : arrays)
        {
            if(i[0] < min)
            {
                min = i[0];
            }

            if(i[i.size() - 1] > max)
            {
                max = i[i.size() - 1];
            }
        }
        return max - min;
    }
};

代码逻辑

初始化：min 和 max 分别被初始化为一个较大的值和一个较小的值，用于记录所有数组中的最小值和最大值。
遍历数组：对于每个数组，检查其第一个元素（最小值）和最后一个元素（最大值），并更新全局的 min 和 max。
返回结果：最终返回 max - min，即最大值与最小值的差。

问题分析

未检查最小值和最大值是否来自同一个数组：
- 初始代码只记录了全局的最小值和最大值，但没有检查它们是否来自同一个数组。
- 如果最小值和最大值来自同一个数组，那么计算结果是不符合要求的，因为题目要求最小值和最大值必须来自不同的数组。
无法处理边界情况：
- 如果所有数组的最小值和最大值都来自同一个数组，初始代码无法正确处理这种情况，导致结果错误。

修改后的代码

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int min_val = 10001;
        int max_val = -10001;
        int min_idx = -1;
        int max_idx = -1;

        // 遍历所有数组，找到最小值和最大值以及它们所在的数组索引
        for (int i = 0; i < arrays.size(); ++i) {
            if (arrays[i][0] < min_val) {
                min_val = arrays[i][0];
                min_idx = i;
            }
            if (arrays[i][arrays[i].size() - 1] > max_val) {
                max_val = arrays[i][arrays[i].size() - 1];
                max_idx = i;
            }
        }

        // 如果最小值和最大值不在同一个数组中，直接返回它们的差值
        if (min_idx != max_idx) {
            return max_val - min_val;
        }

        // 如果最小值和最大值在同一个数组中，需要找到次小值和次大值
        int second_min_val = 10001;
        int second_max_val = -10001;

        for (int i = 0; i < arrays.size(); ++i) {
            if (i != min_idx) {
                if (arrays[i][0] < second_min_val) {
                    second_min_val = arrays[i][0];
                }
            }
            if(i != max_idx)
            {
                if (arrays[i][arrays[i].size() - 1] > second_max_val) {
                    second_max_val = arrays[i][arrays[i].size() - 1];
                }
            }
        }

        // 返回最大值与次小值的差值和次大值与最小值的差值中的较大者
        return std::max(max_val - second_min_val, second_max_val - min_val);
    }
};

代码逻辑

初始化：
- min_val 和 max_val 用于记录全局的最小值和最大值。
- min_idx 和 max_idx 用于记录最小值和最大值所在的数组索引。
第一次遍历：
- 遍历所有数组，找到全局的最小值和最大值，并记录它们所在的数组索引。
检查是否来自同一个数组：
- 如果最小值和最大值不在同一个数组中，直接返回它们的差值。
处理最小值和最大值在同一个数组的情况：
- 如果最小值和最大值来自同一个数组，则需要找到次小值和次大值（即排除当前数组的最小值和最大值）。
- 再次遍历数组，跳过最小值和最大值所在的数组，找到次小值和次大值。
返回结果：
- 返回 max_val - second_min_val 和 second_max_val - min_val 中的较大者，确保最小值和最大值来自不同的数组。