624. Maximum-Distance-in-Arrays.md

题目

思路

顺序扫描这 m 个数组，当扫描到第 i 个数组时，计算出 m[i] 中最小的元素和前 i - 1 个数组中最大的元素 max_val 的差的绝对值，以及 m[i] 中最大的元素和前 i - 1 个数组中最小的元素 min_val 的差的绝对值。

在这之后，我们更新 min_val 和 max_val，使其变为前 i 个数组中最小和最大的元素。

• 时间复杂度：O(M)，其中 M是数组的个数。
• 空间复杂度：O(1)。

图解：

代码

class Solution(object):
    def maxDistance(self, arrays):
        """
        :type arrays: List[List[int]]
        :rtype: int
        """
        # cur_max,cur_min: 记录当前最大值和当前最小值
        # res：最终结果
        if len(arrays) < 2:
            return 0
        cur_max, cur_min = arrays[0][-1], arrays[0][0]
        res = 0
        for i in range(1, len(arrays)):
            tmp_min, tmp_max = arrays[i][0], arrays[i][-1]  # 当前的最大值与最小值
            res = max(res, abs(cur_max - tmp_min), abs(tmp_max - cur_min)) # 核心逻辑
            cur_max = max(cur_max, tmp_max) # 更新当前最大值与最小值
            cur_min = min(cur_min, tmp_min)
        return res


print(Solution().maxDistance([[-8, -7, -7, -5, 1, 1, 3, 4],
                              [-2],
                              [-10, -10, -7, 0, 1, 3],
                              [2]]))