LeetCode 624 数组列表中的最大距离费曼学习法思路假装给零基础小白讲明白先看懂题意、先写暴力法理解问题发现暴力超时再挖掘题目隐藏条件每个数组升序推出贪心最优解找到卡点、讲清楚为什么不用遍历全部元素。一、原题信息题号624 题目名称数组列表中的最大距离Maximum Distance in Arrays题目描述给定m个数组每个数组已经按照升序排好序。现在你需要从两个不同数组中各挑选一个整数一个数组选一个计算距离两个数字a、b距离定义为绝对值|a-b|。请返回可以得到的最大距离。示例1输入[[1,2,3],[4,5],[1,2,3]]输出4解释从第1/3数组取1第二个数组取5|1-5|4示例2输入[[1],[1]]输出0提示约束m arrays.length2≤m≤1052 \le m \le 10^52≤m≤1051≤arrays[i].length≤5001 \le arrays[i].length \le 5001≤arrays[i].length≤500−104≤arrays[i][j]≤104-10^4 \le arrays[i][j] \le 10^4−104≤arrays[i][j]≤104每个arrays[i]升序排序所有数组内整数总数最多10510^5105二、费曼学习法分步破解题目步骤1先理解问题小白视角通俗翻译有好多排好序的小列表。必须两个不同列表各拿一个数字算两数差的绝对值找最大的那个绝对值。❗重点限制不能同一个数组拿两个数第一想法暴力解法最容易想到但是大数据超时思路两两枚举所有不同的数组对数组i数组ji≠j对于这一对数组遍历数组i全部元素遍历数组j全部元素计算|x-y|记录最大值最后返回最大值但是约束中数组数量可以到10510^5105两两枚举数组是O(m2)O(m^2)O(m2)直接爆炸肯定超时。发现盲点题目说了每个数组升序这个条件就是突破口。重要数学结论核心必须理解单个数组升序数组最小值第一个元素 arr[0]数组最大值最后一个元素 arr[-1]任意两个不同数组A、BA的min、A的maxB的min、B的max两个数组之间的最大绝对值差只会是下面两个候选之一max(∣Amax−Bmin∣, ∣Amin−Bmax∣)\max( |A_{max}-B_{min}|,\ |A_{min}-B_{max}| )max(∣Amax−Bmin∣,∣Amin−Bmax∣)不用遍历数组里面所有数字只需要拿每个数组的头尾两个数。一句话给小孩解释一个从小到大排好队的队伍最大最小一定站在队伍两头最远的差距只会发生在两头之间。暴力优化版本不再遍历数组内部全部元素只拿每个数组的首尾。时间复杂度O(m2)O(m^2)O(m2)数组很多的时候依然超时。步骤2贪心思路最优解O(m)只遍历一遍数组核心思想边遍历数组边维护前面所有数组的全局最小、全局最大流程拿第一个数组的头尾初始化global_min前面所有数组最小值、global_max前面所有数组最大值从第二个数组开始循环遍历当前数组cur_min arr[0]cur_max arr[-1]计算两个候选距离候选1当前数组最大值 - 历史全局最小值abs(cur_max - global_min)候选2历史全局最大值 - 当前数组最小值abs(global_max - cur_min)拿这两个候选更新全局最大距离max_dist更新global_min和global_max把当前数组的min、max纳入历史范围给下一轮数组使用遍历全部数组结束返回max_dist✅ 为什么这个方法不会选同一个数组的两个元素历史的global_min / global_max全部来自前面已经遍历过的数组当前数组是新数组。所以一定是不同数组的元素做差值满足题目的限制这是最巧妙的地方。费曼自检有没有漏洞假设全局最大和全局最小值刚好来自当前数组不会global_min/max是上一轮保存的是前面数组的数据当前数组还没有更新进去计算候选距离的时候历史和当前天然属于不同数组。计算完距离才更新global_min/max。手动走一遍样例[[1,2,3],[4,5],[1,2,3]]初始化第一个数组 [1,2,3]global_min 1global_max3max_dist0第二个数组 [4,5]cur_min4cur_max5候选1abs(5 - 1) 4候选2abs(3 - 4) 1max_dist更新为4更新global_min min(1,4)1global_maxmax(3,5)5第三个数组 [1,2,3]cur_min1cur_max3候选1abs(3 - 1)2候选2abs(5 -1)4max_dist仍然是4更新global_minmin(1,1)1global_maxmax(5,3)5遍历结束返回4 ✔三、Python代码每行详细注释贪心最优解法通过所有测试用例# 导入类型注解工具LeetCode平台需要List类型声明fromtypingimportListclassSolution:# 定义函数输入是二维列表arrays返回int整数defmaxDistance(self,arrays:List[List[int]])-int:# 初始化取第一个数组的最小值数组第一个元素global_minarrays[0][0]# 初始化取第一个数组的最大值数组最后一个元素global_maxarrays[0][-1]# 初始化最大距离默认0max_dist0# 从第2个数组开始遍历下标从1开始0号已经用来初始化了foriinrange(1,len(arrays)):# 获取当前遍历数组cur_arrarrays[i]# 当前数组最小值升序数组第一个元素cur_mincur_arr[0]# 当前数组最大值升序数组最后一个元素cur_maxcur_arr[-1]# 候选距离1当前数组最大值 和 历史所有数组的最小值 的绝对值差candidate1abs(cur_max-global_min)# 候选距离2历史所有数组最大值 和 当前数组最小值 的绝对值差candidate2abs(global_max-cur_min)# 更新全局最大距离在旧max_dist、候选1、候选2三者取最大max_distmax(max_dist,candidate1,candidate2)# 更新全局最小值对比旧global_min 和 当前数组最小值保留更小值global_minmin(global_min,cur_min)# 更新全局最大值对比旧global_max 和 当前数组最大值保留更大值global_maxmax(global_max,cur_max)# 遍历全部数组完成返回最终最大距离returnmax_dist# 测试样例 调用代码 if__name____main__:solSolution()# 测试样例1test1[[1,2,3],[4,5],[1,2,3]]print(sol.maxDistance(test1))#输出4# 测试样例2test2[[1],[1]]print(sol.maxDistance(test2))#输出0# 额外测试用例test3[[-1,5],[1,2,3]]print(sol.maxDistance(test3))# |5-1|4暴力优化版代码仅教学大数据会超时帮助理解只拿每个数组头尾两两枚举数组适合理解原理但是数组量大的时候O(m²)超时不能提交大数据fromtypingimportListclassSolution:defmaxDistance(self,arrays:List[List[int]])-int:max_dist0# 预先提取每个数组的最小、最大值存成列表minmax_list[]forarrinarrays:minmax_list.append((arr[0],arr[-1]))mlen(minmax_list)# 两层循环枚举ij两组不同数组foriinrange(m):amin,amaxminmax_list[i]forjinrange(i1,m):bmin,bmaxminmax_list[j]# 两个数组之间的最大距离只有两个候选d1abs(amax-bmin)d2abs(amin-bmax)current_maxmax(d1,d2)ifcurrent_maxmax_dist:max_distcurrent_maxreturnmax_dist四、复杂度分析贪心最优解时间复杂度O(m)O(m)O(m)m是数组个数只循环遍历一遍所有数组每个数组只取头尾两个元素不遍历内部元素空间复杂度O(1)O(1)O(1)只使用固定几个变量额外空间不随输入变大而增长暴力优化版本时间复杂度O(m2)O(m^2)O(m2)数组量大时直接超时只能用于学习理解逻辑五、应用场景举例这个模型对应多组有序采样数据跨组找最大波动差值物联网传感器多个传感器每个传感器采集的时序数据已经按时间排序求不同传感器读数之间最大差值。比如传感器A、B、C各自采集温度有序序列找两个不同传感器的温度最大差值。金融行情多只股票每只股票一段时间内的价格序列按时间排序跨股票找最大价格差距。统计分析多组实验样本每组样本有序寻找两组样本极值的最大差距。后端业务多批有序日志数据不同批次之间找数值最大跨度。业务价值不用扫描每组全部数据只拿每组的首尾极值一遍遍历算出跨集合最大差距节省大量计算。六、费曼复盘自己给自己提问检验理解Q为什么不用比较abs(cur_max - global_max)A这两个值来自同一侧极值差值一定不会是最大最大差值一定是一大一小跨数组。Q为什么更新global_min、global_max必须在计算候选距离之后A如果先更新global_min就包含当前数组的值候选距离就变成同一个数组内部元素违反题目规则。先算差值再更新历史极值是这题最容易踩坑的地方。Q数组只有一个元素如[[1],[1]]代码还能正常跑吗A可以。数组只有单个元素arr[0]和arr[-1]是同一个值逻辑不变。
LeetCode 624 数组列表中的最大距离
LeetCode 624 数组列表中的最大距离费曼学习法思路假装给零基础小白讲明白先看懂题意、先写暴力法理解问题发现暴力超时再挖掘题目隐藏条件每个数组升序推出贪心最优解找到卡点、讲清楚为什么不用遍历全部元素。一、原题信息题号624 题目名称数组列表中的最大距离Maximum Distance in Arrays题目描述给定m个数组每个数组已经按照升序排好序。现在你需要从两个不同数组中各挑选一个整数一个数组选一个计算距离两个数字a、b距离定义为绝对值|a-b|。请返回可以得到的最大距离。示例1输入[[1,2,3],[4,5],[1,2,3]]输出4解释从第1/3数组取1第二个数组取5|1-5|4示例2输入[[1],[1]]输出0提示约束m arrays.length2≤m≤1052 \le m \le 10^52≤m≤1051≤arrays[i].length≤5001 \le arrays[i].length \le 5001≤arrays[i].length≤500−104≤arrays[i][j]≤104-10^4 \le arrays[i][j] \le 10^4−104≤arrays[i][j]≤104每个arrays[i]升序排序所有数组内整数总数最多10510^5105二、费曼学习法分步破解题目步骤1先理解问题小白视角通俗翻译有好多排好序的小列表。必须两个不同列表各拿一个数字算两数差的绝对值找最大的那个绝对值。❗重点限制不能同一个数组拿两个数第一想法暴力解法最容易想到但是大数据超时思路两两枚举所有不同的数组对数组i数组ji≠j对于这一对数组遍历数组i全部元素遍历数组j全部元素计算|x-y|记录最大值最后返回最大值但是约束中数组数量可以到10510^5105两两枚举数组是O(m2)O(m^2)O(m2)直接爆炸肯定超时。发现盲点题目说了每个数组升序这个条件就是突破口。重要数学结论核心必须理解单个数组升序数组最小值第一个元素 arr[0]数组最大值最后一个元素 arr[-1]任意两个不同数组A、BA的min、A的maxB的min、B的max两个数组之间的最大绝对值差只会是下面两个候选之一max(∣Amax−Bmin∣, ∣Amin−Bmax∣)\max( |A_{max}-B_{min}|,\ |A_{min}-B_{max}| )max(∣Amax−Bmin∣,∣Amin−Bmax∣)不用遍历数组里面所有数字只需要拿每个数组的头尾两个数。一句话给小孩解释一个从小到大排好队的队伍最大最小一定站在队伍两头最远的差距只会发生在两头之间。暴力优化版本不再遍历数组内部全部元素只拿每个数组的首尾。时间复杂度O(m2)O(m^2)O(m2)数组很多的时候依然超时。步骤2贪心思路最优解O(m)只遍历一遍数组核心思想边遍历数组边维护前面所有数组的全局最小、全局最大流程拿第一个数组的头尾初始化global_min前面所有数组最小值、global_max前面所有数组最大值从第二个数组开始循环遍历当前数组cur_min arr[0]cur_max arr[-1]计算两个候选距离候选1当前数组最大值 - 历史全局最小值abs(cur_max - global_min)候选2历史全局最大值 - 当前数组最小值abs(global_max - cur_min)拿这两个候选更新全局最大距离max_dist更新global_min和global_max把当前数组的min、max纳入历史范围给下一轮数组使用遍历全部数组结束返回max_dist✅ 为什么这个方法不会选同一个数组的两个元素历史的global_min / global_max全部来自前面已经遍历过的数组当前数组是新数组。所以一定是不同数组的元素做差值满足题目的限制这是最巧妙的地方。费曼自检有没有漏洞假设全局最大和全局最小值刚好来自当前数组不会global_min/max是上一轮保存的是前面数组的数据当前数组还没有更新进去计算候选距离的时候历史和当前天然属于不同数组。计算完距离才更新global_min/max。手动走一遍样例[[1,2,3],[4,5],[1,2,3]]初始化第一个数组 [1,2,3]global_min 1global_max3max_dist0第二个数组 [4,5]cur_min4cur_max5候选1abs(5 - 1) 4候选2abs(3 - 4) 1max_dist更新为4更新global_min min(1,4)1global_maxmax(3,5)5第三个数组 [1,2,3]cur_min1cur_max3候选1abs(3 - 1)2候选2abs(5 -1)4max_dist仍然是4更新global_minmin(1,1)1global_maxmax(5,3)5遍历结束返回4 ✔三、Python代码每行详细注释贪心最优解法通过所有测试用例# 导入类型注解工具LeetCode平台需要List类型声明fromtypingimportListclassSolution:# 定义函数输入是二维列表arrays返回int整数defmaxDistance(self,arrays:List[List[int]])-int:# 初始化取第一个数组的最小值数组第一个元素global_minarrays[0][0]# 初始化取第一个数组的最大值数组最后一个元素global_maxarrays[0][-1]# 初始化最大距离默认0max_dist0# 从第2个数组开始遍历下标从1开始0号已经用来初始化了foriinrange(1,len(arrays)):# 获取当前遍历数组cur_arrarrays[i]# 当前数组最小值升序数组第一个元素cur_mincur_arr[0]# 当前数组最大值升序数组最后一个元素cur_maxcur_arr[-1]# 候选距离1当前数组最大值 和 历史所有数组的最小值 的绝对值差candidate1abs(cur_max-global_min)# 候选距离2历史所有数组最大值 和 当前数组最小值 的绝对值差candidate2abs(global_max-cur_min)# 更新全局最大距离在旧max_dist、候选1、候选2三者取最大max_distmax(max_dist,candidate1,candidate2)# 更新全局最小值对比旧global_min 和 当前数组最小值保留更小值global_minmin(global_min,cur_min)# 更新全局最大值对比旧global_max 和 当前数组最大值保留更大值global_maxmax(global_max,cur_max)# 遍历全部数组完成返回最终最大距离returnmax_dist# 测试样例 调用代码 if__name____main__:solSolution()# 测试样例1test1[[1,2,3],[4,5],[1,2,3]]print(sol.maxDistance(test1))#输出4# 测试样例2test2[[1],[1]]print(sol.maxDistance(test2))#输出0# 额外测试用例test3[[-1,5],[1,2,3]]print(sol.maxDistance(test3))# |5-1|4暴力优化版代码仅教学大数据会超时帮助理解只拿每个数组头尾两两枚举数组适合理解原理但是数组量大的时候O(m²)超时不能提交大数据fromtypingimportListclassSolution:defmaxDistance(self,arrays:List[List[int]])-int:max_dist0# 预先提取每个数组的最小、最大值存成列表minmax_list[]forarrinarrays:minmax_list.append((arr[0],arr[-1]))mlen(minmax_list)# 两层循环枚举ij两组不同数组foriinrange(m):amin,amaxminmax_list[i]forjinrange(i1,m):bmin,bmaxminmax_list[j]# 两个数组之间的最大距离只有两个候选d1abs(amax-bmin)d2abs(amin-bmax)current_maxmax(d1,d2)ifcurrent_maxmax_dist:max_distcurrent_maxreturnmax_dist四、复杂度分析贪心最优解时间复杂度O(m)O(m)O(m)m是数组个数只循环遍历一遍所有数组每个数组只取头尾两个元素不遍历内部元素空间复杂度O(1)O(1)O(1)只使用固定几个变量额外空间不随输入变大而增长暴力优化版本时间复杂度O(m2)O(m^2)O(m2)数组量大时直接超时只能用于学习理解逻辑五、应用场景举例这个模型对应多组有序采样数据跨组找最大波动差值物联网传感器多个传感器每个传感器采集的时序数据已经按时间排序求不同传感器读数之间最大差值。比如传感器A、B、C各自采集温度有序序列找两个不同传感器的温度最大差值。金融行情多只股票每只股票一段时间内的价格序列按时间排序跨股票找最大价格差距。统计分析多组实验样本每组样本有序寻找两组样本极值的最大差距。后端业务多批有序日志数据不同批次之间找数值最大跨度。业务价值不用扫描每组全部数据只拿每组的首尾极值一遍遍历算出跨集合最大差距节省大量计算。六、费曼复盘自己给自己提问检验理解Q为什么不用比较abs(cur_max - global_max)A这两个值来自同一侧极值差值一定不会是最大最大差值一定是一大一小跨数组。Q为什么更新global_min、global_max必须在计算候选距离之后A如果先更新global_min就包含当前数组的值候选距离就变成同一个数组内部元素违反题目规则。先算差值再更新历史极值是这题最容易踩坑的地方。Q数组只有一个元素如[[1],[1]]代码还能正常跑吗A可以。数组只有单个元素arr[0]和arr[-1]是同一个值逻辑不变。
 浅谈shell与内核的交互以及对权限的初识)
