Star

LeetCode Weekly Contest 624.Maximum Distance in Arrays

Posted on | In |

Question

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. 

1
2
3
4
5
6
Example 1:
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: Each given array will have at least 1 number. There will be at least two non-empty arrays. The total number of the integers in all the m arrays will be in the range of [2, 10000]. The integers in the m arrays will be in the range of [-10000, 10000].

Explanation

这道题我是暴力解吧，先找到每个array里面的max和min，然后再得到相减最大的值。 在Discuss里面看到很棒的解法，我忽略了是sorted这个条件，在后面附上Discuss里面的解法，就是遍历的时候就同时计算了，非常巧妙。

Code

More Clever Solution： https://discuss.leetcode.com/topic/92859/java-solution-min-and-max 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int maxDistance(int[][] arrays) {
        int result = Integer.MIN_VALUE;
        int max = arrays[0][arrays[0].length - 1];
        int min = arrays[0][0];
        for (int i = 1; i < arrays.length; i++) {
            result = Math.max(result, Math.abs(arrays[i][0] - max));
            result = Math.max(result, Math.abs(arrays[i][arrays[i].length - 1] - min));
            max = Math.max(max, arrays[i][arrays[i].length - 1]);
            min = Math.min(min, arrays[i][0]);
        }
        return result;
    }
}

Stupid Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public int maxDistance(int[][] arrays) {
        int[][] maxMin = new int[arrays.length][2];
        int max = 0;
        if (arrays == null || arrays[0] == null) return 0;
        // Store every max and min in each array
        for (int i=0; i<arrays.length; i++) {
            int partMax = Integer.MIN_VALUE;
            int partMin = Integer.MAX_VALUE;
            for (int j = 0; j< arrays[i].length; j++) {
                if (arrays[i][j] > partMax) {
                    partMax = arrays[i][j];
                }
                if (arrays[i][j] < partMin) {
                    partMin = arrays[i][j];
                }
            }
            maxMin[i][0] = partMax;
            maxMin[i][1] = partMin;
        }
        // use all max and min to calculate result
        for (int i=0; i < maxMin.length; i++) {
            for (int j = 0; j<maxMin.length; j++) {
                if (i != j) {
                    max = Math.max(max, (maxMin[i][0] - maxMin[j][1]));
                }
            }
        }
        return max;
    }
}