adjacent value 邻近值算法问题的 My answe

据说是经典面经问题之一，实际上刚才某位朋友就遇上这道面试难题求助于我了，到最后虽然都没有赶上时间拯救到他（论英语阅读能力的重要性）......Orz

姑且放上原题目和我自己做的答案（未经验证）

Integer V lies strictly between integers U and W if U < V < W or if U > V > W

A non empty zero indexed array A consisting of N integers is given.
A pair of indices (P, Q), where 0 <= P < Q < N, is said to have 'adjacent values'
if no value in the array lies strictly between values A[P] and A[Q],
and in addition A[P] != A[Q]

For example, in array A such that:
A[0] = 0
A[1] = 3
A[2] = 3
A[3] = 7
A[4] = 5
A[5] = 3
A[6] = 11
A[7] = 1

the following pairs of indices have adjacent values:
(0,7), (1,4), (1,7)
(2,4), (2,7), (3,4)
(3,6), (4,5), (5,7)

For example, indices 4 and 5 have adjacent values because the values a[4] = 5 and A[5] = 3 are different
and there is no value in array A that lies strictly between them
the only such value could be the number 4, which is not present in the array

Given two indices P and Q, their distance is defined as abs(P-Q)
where abs(X) = X for X>=0
and abs(X) = -X for X<=0
For example the distance between indices 4 and 5 is 1 because abs(4-5) = abs(5-4) = 1

Write a function that given a non-empty zero-indexed array A consisting of N integers
returns the maximum distance between indices of this array that have adjacent values
The function should return -1 if no adjacent indices exist

For example given array A such that:
A[0] = 1
A[1] = 4
A[2] = 7
A[3] = 3
A[4] = 3
A[5] = 5

the function should return 4 because:

• indices 0 and 4 are adjacent because A[0] != A[4]
  and the array does not contain any value that lies strictly between A[0] = 1 and A[4] = 3
• the distance between these indices is abd(0-4) = 4
• no other pair of adjacent indices that has a larger distance exists

Assume that

• N is an integer within the range [1 .. 40,000]
• each element of array A is an integer within the range [-2,147,483,648 to 2,147,483,647]

class Solution {
    public static int solution(int[] A) {
        int[] valueDistances = new int[A.length];
        int[] distances = new int[A.length];
        int maxDistance = 0;
        Arrays.fill(valueDistances, Integer.MAX_VALUE);

        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                int valueDistance = Math.abs(A[i] - A[j]);
                if (valueDistances[i] >= valueDistance) {
                    valueDistances[i] = valueDistance;
                    distances[i] = Math.abs(i - j);
                    if (distances[i] > maxDistance) {
                        maxDistance = distances[i];
                    }
                }
                if (valueDistances[j] > valueDistance)
                    valueDistances[j] = valueDistance;
            }
        }
        return maxDistance > 0 ? maxDistance : -1;
    }
}