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

题目：

给定 m 个数组，每个数组都已经按照升序排好序了。
现在你需要从两个差别的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离界说为它们差的绝对值 |a-b| 。
返回最大距离。
示例 1：
  

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

复制代码

示例 2：
  

1. <strong>输入：</strong>arrays = [[1],[1]]
2. <strong>输出：</strong>0

复制代码

提示：

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

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

初始代码

1. class Solution {
2. public:
3.     int maxDistance(vector<vector<int>>& arrays) {
4.         int min = 10001;
5.         int max = -10001;
6.         for(auto i : arrays)
7.         {
8.             if(i[0] < min)
9.             {
10.                 min = i[0];
11.             }
13.             if(i[i.size() - 1] > max)
14.             {
15.                 max = i[i.size() - 1];
16.             }
17.         }
18.         return max - min;
19.     }
20. };

复制代码

代码逻辑

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

题目分析

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

---

修改后的代码

1. class Solution {
2. public:
3.     int maxDistance(vector<vector<int>>& arrays) {
4.         int min_val = 10001;
5.         int max_val = -10001;
6.         int min_idx = -1;
7.         int max_idx = -1;
9.         // 遍历所有数组，找到最小值和最大值以及它们所在的数组索引
10.         for (int i = 0; i < arrays.size(); ++i) {
11.             if (arrays[i][0] < min_val) {
12.                 min_val = arrays[i][0];
13.                 min_idx = i;
14.             }
15.             if (arrays[i][arrays[i].size() - 1] > max_val) {
16.                 max_val = arrays[i][arrays[i].size() - 1];
17.                 max_idx = i;
18.             }
19.         }
21.         // 如果最小值和最大值不在同一个数组中，直接返回它们的差值
22.         if (min_idx != max_idx) {
23.             return max_val - min_val;
24.         }
26.         // 如果最小值和最大值在同一个数组中，需要找到次小值和次大值
27.         int second_min_val = 10001;
28.         int second_max_val = -10001;
30.         for (int i = 0; i < arrays.size(); ++i) {
31.             if (i != min_idx) {
32.                 if (arrays[i][0] < second_min_val) {
33.                     second_min_val = arrays[i][0];
34.                 }
35.             }
36.             if(i != max_idx)
37.             {
38.                 if (arrays[i][arrays[i].size() - 1] > second_max_val) {
39.                     second_max_val = arrays[i][arrays[i].size() - 1];
40.                 }
41.             }
42.         }
44.         // 返回最大值与次小值的差值和次大值与最小值的差值中的较大者
45.         return std::max(max_val - second_min_val, second_max_val - min_val);
46.     }
47. };

复制代码

代码逻辑

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

改进点

• 确保最小值和最大值来自差别数组：
  
  
  
  • 通过记录最小值和最大值地点的数组索引，可以判断它们是否来自同一个数组。
    
  • 如果来自同一个数组，则通过次小值和次大值来重新计算最大距离。
    
  
  
• 处理惩罚界限环境：
  
  
  
  • 修改后的代码能够正确处理惩罚所有数组的最小值和最大值都来自同一个数组的环境。
    
  
  

---

总结

• 初始代码的题目：
  
  
  
  • 未检查最小值和最大值是否来自同一个数组。
    
  • 无法处理惩罚所有数组的最小值和最大值都来自同一个数组的环境。
    
  
  
• 修改后的代码的改进：
  
  
  
  • 通过记录数组索引，确保最小值和最大值来自差别的数组。
    
  • 引入次小值和次大值的概念，处理惩罚界限环境。
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。