Max Distance

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].

If there is no solution possible, return -1.

A : [3 5 4 2]

Output : 2 
for the pair (3, 4)

思路:

建立两个单调array。对于Array中的每个element来说，如果之前有它小的element，那么我们不会考虑它作为i。如果之后有比它大的element，那么我们也不会选它做j。

所以我们建立两个array，一个minArr，一个maxArr。minArr保存直到当前index i最小的element。maxArr保存直到当前index j（从右往左）最大的element。

然后我们同时从左往右scan这两个array。如果minArr[i] <= maxArr[j]，那就是一个valid的情况，我们可以更新maxgap，同时j++，来找更大的j - i。如果minArr[i] > maxArr[j]，那么我们需要更小的minArr[i]，所以i++。

solution:

Time: O(n)
Space: O(n)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int maximumGap(final List<Integer> A) {
        //  3 5 4 2
        // [3 3 3 2] - min
        // [5 5 4 2] - max
        int[] minArr = new int[A.size()];
        int[] maxArr = new int[A.size()];
        minArr[0] = A.get(0);
        maxArr[A.size() - 1] = A.get(A.size() - 1);
        for (int i = 1; i < A.size(); i ++) {
            minArr[i] = Math.min(A.get(i), minArr[i - 1]);
        }
        for (int i = A.size() - 2; i >= 0; i --) {
            maxArr[i] = Math.max(A.get(i), maxArr[i + 1]);
        }
        int i = 0, j = 0, maxGap = -1;
        while (i < A.size() && j < A.size()) {
            if (minArr[i] <= maxArr[j]) {
                maxGap = Math.max(maxGap, j - i);
                j ++;
            } else {
                i ++;
            }
        }
        return maxGap;
    }
}