MaximumDistanceInArrays [source code]

public class MaximumDistanceInArrays {
static
/******************************************************************************/
public class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        List<List<Integer>> res = new ArrayList<>();
        int n = arrays.size();
        int minMin = Integer.MAX_VALUE, maxMax = Integer.MIN_VALUE;
        List<Integer> lsMin = new ArrayList<>();
        List<Integer> lsMax = new ArrayList<>();
        for (List<Integer> ls : arrays) {
            int index = arrays.indexOf(ls);
            int thisMin = ls.get(0), thisMax = ls.get(ls.size() - 1);
            if (thisMin < minMin) {
                minMin = thisMin;
                lsMin.clear();
                lsMin.add(index);
            } else if (thisMin == minMin) {
                lsMin.add(index);
            }
            if (thisMax > maxMax) {
                maxMax = thisMax;
                lsMax.clear();
                lsMax.add(index);
            } else if (thisMax == maxMax) {
                lsMax.add(index);
            }
        }
        int accum = 0;
        for (int i : lsMin) accum ^= i;
        for (int i : lsMax) accum ^= i;
        if (accum != 0 || (accum == 0 && lsMin.size() > 1)) return maxMax - minMin;
        //minMin and maxMax in same list: either one of them will be in the maximum distance
        int avoidIndex = lsMin.get(0);
        int secondMin = Integer.MAX_VALUE, secondMax = Integer.MIN_VALUE;
        for (int i = 0; i < arrays.size(); i++) {
            if (i == avoidIndex) continue;
            List<Integer> ls = arrays.get(i);
            int thisMin = ls.get(0), thisMax = ls.get(ls.size() - 1);
            if (thisMin < secondMin) secondMin = thisMin;
            if (thisMax > secondMax) secondMax = thisMax;
        }
        return Math.max(Math.abs(maxMax - secondMin), Math.abs(minMin - secondMax));
    }
}
/******************************************************************************/

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

做算法都是从 naive 的思路开始写, 只有当 naive 的思路出现问题的时候, 你才知道你少考虑了什么东西;

这个问题还是想的太复杂了, 而且虽然我一直强调, 从暴力解开始, 但是我这个问题上面还是太急于想出一个聪明的解法, 在暴力解上面没有花多少时间, 导致最后对问题的理解完全是过于复杂了; 不过这个算法最后还是写出来了, 就是速度太差了: 155(4).

首先这个问题的最暴力的解很简单, 就是一个数跟另外一个数, 穷举的去比较. 但是这个没有利用 sorted 的性质, 那么更好的一个解法就是每两个 list 之间进行比较, A 的头和 B 的尾相减, 然后 B 的头和 A 的尾相减, 取两者最大值; 能够想到这个做法, 其实就跟最优解不远了;
最优解就是把这个pair-wise穷举做到一个 pass 里面; 因为我们只要找一个最大 distance, 当我们走到一个 list 的时候, 前面的所有 list 对我们唯一有用的信息就是他们的head 当中最小的是多少, 以及它们的 tail 当中最大的是多少(因为我们这里 head 跟 tail 其实是等价的作用, 所以不用在意 minHead and maxTail是否属于同一个 list: 我们只在乎 value).

这个问题其实如果用 DP的思路也可以思考, 不过类似所有的 DPI 问题, 这里的 DP value 的选择要有讲究. 肯定不能直接就用max distance, 这个并没有 DP Property; 这里最后实际上的DP value 其实就是两个最大值最小值. 这两个 DP value 可以直接用来计算我们最后希望得到的value, 虽然计算方式可能稍微有点隐晦.

另外在 editorial 的解法的 illustration 上面, 还学到了一个看法. 以前看到 sorted 的, 一般顶多想想2pointers 这种东西; 现在知道如果再碰到这种 sorted, 在自己脑子里思考的时候的 visualization 可以适当考虑用 interval 的概念来显示(类似于 scheduling 里面的 interval. 即使我们这里的这个sorted list其实并不是完整连续的).

总体来说这个问题还是想的太复杂了, 而且没有抓到问题的核心思考方式; 我上来就想着既然是 sorted, 就用两个array of mins/maxes来代表这个二维 list 的所有信息. 这个想法从一开始就是错的, 一看到 sorted 就认为只要记住最值分析最值就行了, 这就是遗漏了很多问题的关键信息;
这个问题跟大部分的 bipartite matching 问题很相似, 可以用一种类似代表队的思路去思考: 每个 list 出一个代表, 进行计算, 所以最后他们的解得到的思路就是在第一维上 iterate, 也就是对队伍进行 iterate; 只看一个维度(往往是最高维), 问题反而好像是简单了很多;
我上来的时候脑子里的全都是第二维的 element, 也就是二维表格的 entry, 最后就丢失重点了;

这里多说一句, 为什么要讲 visualization的事情, 因为尤其是这种数字的题目, 有些时候你就死盯着数字本身看, 是不容易看出来规律的, 有时候在脑子里大概鼓捣一点 visual, 是可以帮助更好的理解问题的, 比如这里的 interval 的移动, 比如如果是一个sorted array, 那么类似三角形的 visual;

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