maximum-distance-in-array

Maximum Distance in Array – LeetCode 624

Problem

Description

Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.

Answer

Original

Code

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int res = 0, start = arrays[0][0], end = arrays[0].back();
        for (int i = 1; i < arrays.size(); ++i) {
            start = min(start, arrays[i][0]);
            end = max(end, arrays[i].back());
        }
        return end - start;
    }
};

思路

简单的遍历寻找最大区间。时间复杂度$O(n)$，空间复杂度$O(1)$。

Better

思路

还没看到更好的思路