【Leetcode】624.Maximum Distance in Arrays

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.

Example

Input:
[[1,2,3],
[4,5],
[1,2,3]]
Output: 4
Explanation:
One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Note

1.Each given array will have at least 1 number. There will be at least two non-empty arrays.
2.The total number of the integers in all the m arrays will be in the range of [2, 10000].
3.The integers in the m arrays will be in the range of [-10000, 10000].

Solution

First

public int maxDistance(List<List<Integer>> arrays) {
        if (arrays == null) {
            return 0;
        }
        if (arrays.size() == 1) {
            List<Integer> list = arrays.get(0);
            return list.get(list.size() - 1) - list.get(0);
        }
        int len = arrays.size();
        int max = 0;
        for (int i = 0; i < arrays.size(); i++) {
            int tempFirst = arrays.get(i).get(0);
            for (int j = 0; j < arrays.size(); j++) {
                if (i == j) {
                    continue;
                }
                List<Integer> curList = arrays.get(j);
                int curLast = curList.get(curList.size() - 1);
                if (Math.abs(curLast - tempFirst) > max) {
                    max = curLast - tempFirst;
                }
            }
        }
        return max;
    }

Result

TLE

Analyse

出现TLE，查询得出LC里可能因为复杂度要求不高，由于默认的输入List就是递增的，想到适用两个数组来存每个list的最小和最大值。

Second

public int maxDistance_(List<List<Integer>> arrays) {
        if (arrays == null) {
            return 0;
        }
        if (arrays.size() == 1) {
            List<Integer> list = arrays.get(0);
            return list.get(list.size() - 1) - list.get(0);
        }
        int[] minArray = new int[arrays.size()];
        int[] maxArray = new int[arrays.size()];
        for (int i = 0; i < arrays.size(); i++) {
            List<Integer> array = arrays.get(i);
            minArray[i] = array.get(0);
            maxArray[i] = array.get(array.size() - 1);
        }
        Arrays.sort(minArray);
        Arrays.sort(maxArray);
        int max = maxArray[maxArray.length - 1] - minArray[0];
        return (max > 0) ? max : 0;
    }

Result

WA

Analyse

这里没有考虑到可能来自一个组的刚好组成了最小和最大，就不符合题目要求。

Last

public int maxDistance_(List<List<Integer>> arrays) {
        if (arrays == null) {
            return 0;
        }
        if (arrays.size() == 1) {
            List<Integer> list = arrays.get(0);
            return list.get(list.size() - 1) - list.get(0);
        }
        int[] minArray = new int[arrays.size()];
        int[] maxArray = new int[arrays.size()];
        for (int i = 0; i < arrays.size(); i++) {
            List<Integer> array = arrays.get(i);
            minArray[i] = array.get(0);
            maxArray[i] = array.get(array.size() - 1);
        }
        int max = 0;
        for (int i = 0; i < minArray.length; i++) {
            for (int j = 0; j < maxArray.length; j++) {
                if (i == j) {
                    continue;
                }
                max = maxArray[j] - minArray[i] > max ? maxArray[j] - minArray[i] : max;
            }
        }
        return (max > 0) ? max : 0;
    }

Result

AC

Analyse

这里就是用两个数组存储然后再比较，这里的时间复杂度是O(n^2)，其实和第一个也类似，可能这里稍微代码更简洁。

Optimization

Idea

想要把O(n^2)的复杂度降低，就只需要一个for，需要在一次遍历的时候就能得到结果，就可以降低到O(n)。

public int maxDistance(List<List<Integer>> arrays) {
        if (arrays == null) {
            return 0;
        }
        if (arrays.size() == 1) {
            List<Integer> list = arrays.get(0);
            return list.get(list.size() - 1) - list.get(0);
        }
        int min = arrays.get(0).get(0);
        int max = arrays.get(0).get(arrays.get(0).size() - 1);
        int result = Integer.MIN_VALUE;
        for (int i = 1; i < arrays.size(); i++) {
            result = Math.max(result, Math.abs(arrays.get(i).get(0) - max));
            result = Math.max(result, Math.abs(arrays.get(i).get(arrays.get(i).size() - 1) - min));
            min = Math.min(min, arrays.get(i).get(0));
            max = Math.max(max, arrays.get(i).get(arrays.get(i).size() - 1));
        }
        return result;
    }

Analyse

第一次就得min和max值，然后每次result都交叉两次比较，比较完之后，更新本次之后的min和max值。