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

Categories:

题目描述
思路分析
1. 解法一：贪心（推荐）
相似题目

题目描述

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

思路分析

解法一：贪心（推荐）

核心思路：

每个子数组已按升序排列，最大距离只能来自不同数组的最小值与最大值之差

遍历时维护已遍历数组中的全局最小值 minVal 和全局最大值 maxVal

对当前数组，候选答案为 curMax - minVal 和 maxVal - curMin，取最大值更新答案

处理完当前数组后，更新 minVal 和 maxVal（顺序不能颠倒，避免同数组内取值）

复杂度分析：

时间复杂度：O(m)，其中 m 表示数组列表的总长度（所有子数组元素个数之和）

空间复杂度：O(1)，只使用常数额外空间

class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int minVal = arrays.get(0).get(0);
        int maxVal = arrays.get(0).get(arrays.get(0).size() - 1);
        int result = 0;

        for (int i = 1; i < arrays.size(); i++) {
            List<Integer> arr = arrays.get(i);
            int curMin = arr.get(0);
            int curMax = arr.get(arr.size() - 1);

            // 当前数组最大值 - 已遍历最小值
            result = Math.max(result, curMax - minVal);
            // 已遍历最大值 - 当前数组最小值
            result = Math.max(result, maxVal - curMin);

            // 更新全局最小值和最大值
            minVal = Math.min(minVal, curMin);
            maxVal = Math.max(maxVal, curMax);
        }

        return result;
    }
}

func maxDistance(arrays [][]int) int {
    minVal := arrays[0][0]
    maxVal := arrays[0][len(arrays[0])-1]
    result := 0

    for i := 1; i < len(arrays); i++ {
        arr := arrays[i]
        curMin := arr[0]
        curMax := arr[len(arr)-1]

        // 当前数组最大值 - 已遍历最小值
        if curMax-minVal > result {
            result = curMax - minVal
        }
        // 已遍历最大值 - 当前数组最小值
        if maxVal-curMin > result {
            result = maxVal - curMin
        }

        // 更新全局最小值和最大值
        if curMin < minVal {
            minVal = curMin
        }
        if curMax > maxVal {
            maxVal = curMax
        }
    }

    return result
}

相似题目

题目	难度	考察点
11. 盛最多水的容器	中等	贪心、双指针
53. 最大子数组和	中等	贪心、动态规划
561. 数组拆分	简单	贪心、排序
122. 买卖股票的最佳时机 II	中等	贪心
455. 分发饼干	简单	贪心、排序
1007. 行相等的最少多米诺旋转	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/39881429