Leetcode 624

题目要求

核心算法和原理

• 由于题目要求从两个不同的数组里取，则遍历数组时，每一次遍历都分别计算一下「以此数组的首尾元素为最小/大值的情况下的最大距离」，保证穷尽俩最值不在同一数组的情况，这样遍历一遍即可

• 第一次做的思路是在第一次遍历的时候记录最值所在的数组的索引，然后判断索引是否相同，如果相同则再遍历一遍，这次记录「第二大 / 小的值」 其实就是记录前二大/小的值和索引，如果最值所在idx相同则取 max(top1Max - top2Min, top2Max - top1Min)

代码

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
        int maxAll = -10001, maxCur= -10001;
        int minAll = 10001, minCur = 10001;
        int maxDis = -1;
        for (auto arr : arrays) {
            maxCur = arr.back();
            minCur = arr.front();
            maxDis = max(maxDis, max(maxCur - minAll, maxAll - minCur));
            maxAll = max(maxCur, maxAll);
            minAll = min(minCur, minAll);
        }
        return maxDis;
    }
};