当前位置：首页 > article >正文

leetcode 624. 数组列表中的最大距离

article 2025/1/6 19:06:30

题目如下
在这里插入图片描述
数据范围

这道题又是贪心算法 想得到最大距离第一时间就能想到用最大值减去最小值。
现有两个数组
[1,2,3,4,5,6,7]
[2,3,4,5,6,7,8]
这两个数组的最大距离为7,其中左端为1 右端为8。(现简称左端为l 右端为r)
若加入第三个数组现在思考l和r移动的方向:(只考虑使得(r - l)增大的情况)
1.l向左移动 r不变
2.l不变 r向右移动
3.l向左移动 r向右移动(与题设矛盾排除)
比较1,2情况下l - r与原来l - r的大小
究其根本就是在增加数组的过程改变了最小值和最大值(相对的最大值和最小值因为真正的最大值和最小值可能在同一个数组内部不一定会考虑 所以得到的是局部的最优解)
这个时候我们能得到当n=3时l - r的最大值。而这个解也是n = 3的最优解。
以此类推 当n = m(m是正整数)时只要一直新增数组移动l r最终就能得到全局最优解。

通过代码

class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
        int min1 = arrays[0][0],max1 = arrays[0].back();
        int ans = -1;

        for(int i = 1;i < arrays.size();i++) {
            ans = max(max(abs(arrays[i].back() - min1),abs(arrays[i][0] - max1)),ans);
            max1 = max(arrays[i].back(),max1);
            min1 = min(arrays[i][0],min1);

        }
    return ans;

}
};