MaximumDistanceInArrays2 [source code]

public class MaximumDistanceInArrays2 {
static
/******************************************************************************/
public class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int res = 0, min = arrays.get(0).get(0), max = arrays.get(0).get(arrays.get(0).size() - 1);
        for (int i = 1; i < arrays.size(); i++) {
            List<Integer> ls = arrays.get(i);
            int len = ls.size();
            int distance1 = Math.abs(ls.get(0) - max);
            int distance2 = Math.abs(ls.get(len - 1) - min);
            if (distance1 > res) res = distance1;
            if (distance2 > res) res = distance2;
            min = Math.min(min, ls.get(0));
            max = Math.max(max, ls.get(len - 1));
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MaximumDistanceInArrays2.Solution tester = new MaximumDistanceInArrays2.Solution();
    }
}

这个是 editorial的 solution; 非常的简练; 最后的速度是18ms (73%); 这个问题我还是想的太复杂了;

这个是 discussion 上面一个不使用 abs 的版本:

public class Solution {  
    public int maxDistance(List<List<Integer>> arrays) {  
        int min = Integer.MAX_VALUE;  
        int max = Integer.MIN_VALUE;  
        int res = 0;  
        for(int i = 0;i < arrays.size();i++){  
            List<Integer> array = arrays.get(i);  
            int curMin = array.get(0);  
            int curMax = array.get(array.size()-1);  
            if(max > curMin) res = Math.max(res,max - curMin);//condition 1  
            if(curMax > min) res = Math.max(res,curMax - min);//condition 2  
            min = Math.min(curMin,min);  
            max = Math.max(curMax,max);  
        }  
        return res;  
    }  
}

这个除掉括号的逻辑其实还是比较好的: 如果max <= curMin, 那么就是有一个类似[min..max]..[curMin..curMax]的区间分布, 这种情况下最后能够更新res 的肯定是curMax - min, 所以这个时候干脆就不尝试用max - curMin来更新 res 了;
第二个也是一样的情况;
不过这个优化对于最后的速度的影响并不是特别大;

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.

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].
Difficulty:Easy
Total Accepted:6.1K
Total Submissions:18.6K
Contributor: fallcreek
Companies
yahoo
Related Topics
array hash table