java 找到数组中的最大差异对

Find the max difference pair in the array

提问by OPK

I am working on some kata but I cannot pass all the test cases.

我正在研究一些 kata，但我无法通过所有测试用例。

So the situation is:

所以情况是：

Given any array, such as this array: int[] a = {2, 3, 10, 2, 4, 8, 1}, find the max difference pair in the array, in the meantime make sure the larger value is at the higher index than the lower value.

给定任何数组，例如这个 array: int[] a = {2, 3, 10, 2, 4, 8, 1}，找到数组中的最大差异对，同时确保较大的值位于较高的索引处而不是较低的值。

In this example: 10is the largest element, 1is the smallest, since 10is at index 2, 1is at index 6, so it does not count because the larger pair is at a lower index. So the correct answer is a[0], and a[2], max different is 10-2.

在这个例子中：10是最大的元素，1是最小的，因为10在 index 2，1在 index 6，所以它不计算，因为较大的对在较低的索引处。所以正确答案是a[0]，并且a[2]，最大不同是10-2。

Other requirement is array size Nis between 1and 1_000_000, any given a[i]is between -1_000_000and 1_000_000

其他要求是数组大小N在1和之间1_000_000，任何给定a[i]的在-1_000_000和之间1_000_000

I wrote code like this:

我写了这样的代码：

static int maxDifference(int[] a) {
    //test array size
    if (a.length < 1 || a.length > 1_000_000) return -1;

    int[] oldArr = Arrays.copyOf(a, a.length);
    Arrays.sort(a);
    int max = a[a.length - 1];
    if (max > 1_000_000 || a[0] < -1_000_000) return -1;

    int min = max;
    for (int i = 0; i < oldArr.length; i++) {
        if (oldArr[i] < max) {
            min = Math.min(min, oldArr[i]);
        }
        if (oldArr[i] == max) break;
    }
    int result = min == max ? -1 : max - min;
    return result;
}

My logic is pretty much make a copy of the array and then sort the array, then loop it though, keep a pointer for max and min values, then get the result.

我的逻辑几乎是复制数组，然后对数组进行排序，然后循环它，保留最大值和最小值的指针，然后得到结果。

What is troubling me is I only know there are some test cases I didn't pass, but no hints on why it didn't pass. Can anyone give me some advise and what I may missing in this helper method?

困扰我的是我只知道有些测试用例我没有通过，但没有任何关于它为什么没有通过的提示。谁能给我一些建议以及我在此辅助方法中可能遗漏的内容？

回答by Amit

Basically you need to keep track of the minimum value found so far and the maximum diff found so far:

基本上，您需要跟踪迄今为止发现的最小值和迄今为止发现的最大差异：

static int maxDifference(int[] a) {
    int minimum, diff = -1;
    if(a.length == 0) {
        return -1;
    }
    minimum = a[0];
    for (int i = 1; i < a.length; i++) {
        diff = Math.max(diff, a[i] - minimum);
        minimum = Math.min(minimum, a[i]);
    }
    return diff;
    // depending on interpretation of requirements, above line might be wrong
    // Instead, use:
    // return diff > 0 ? diff : -1;
}

回答by Neuron

If performance is not an issue (what I assume, since you are sorting the array which is probably not the most efficient implementation), this simplebut easily readable piece of code should do the trick:

如果性能不是问题（我假设，因为您正在对数组进行排序，这可能不是最有效的实现），这段简单但易于阅读的代码应该可以解决问题：

public static int maxDifference(int[] a) {
    long bounds = 1_000_000;

    int biggestDifference = -1;
    if(a.length > bounds){
        return -1;
    }
    for (int i = 0; i < a.length-1; i++) {
        if(Math.abs(a[i]) > bounds){
            return -1;
        }
        for (int j = i+1; j < a.length; j++) {
            int difference = Math.abs(a[j] - a[i]);
            if(difference > biggestDifference){
                biggestDifference = difference;
            }
        }
    }
    return biggestDifference;
}

回答by DIA

Answer is:

答案是：

Arrays.sort(this.elements);
maximumDifference = this.elements[this.elements.length-1] - this.elements[0];

回答by MT0

This finds the local minima and maxima and keeps track of the global minima and the position of the current maximum difference.

这会找到局部最小值和最大值，并跟踪全局最小值和当前最大差异的位置。

import java.util.Arrays;

public class MaxDifference {
    private static long difference(
            final int[] array,
            final int minPos,
            final int maxPos
    )
    {
        assert( minPos < maxPos );
        assert( array[minPos] < array[maxPos] );
        return ( (long) array[maxPos] ) - ( (long) array[minPos] );
    }

    public static int[] maxDifference( final int[] array ){
        if ( array == null|| array.length < 2 )
            return null;

        // Position of global minima.
        int minimaPos                 = 0;
        // Value of global minima.
        int minimaValue               = array[0];
        // Position of minima for current maximum difference.
        int minimaPosForMaxDifference = 0;
        // Position of maxima for current maximum difference.
        int maximaPosForMaxDifference = -1;
        // Current maximum difference.
        long maxDifference            = -1;
        // Current position
        int pos                       = 0;


        while ( pos < array.length - 1 ){
            // Find the local minima
            while( pos < array.length - 1 && array[pos] > array[pos + 1])
            {
                pos++;
            }
            // Test if the local minima is the current global minima.
            if ( array[pos] < minimaValue )
            {
              minimaPos   = pos;
              minimaValue = array[pos];
            }

            // Find the local maxima
            while( pos < array.length - 1 && array[pos] <= array[pos + 1])
            {
                pos++;
            }

            if ( pos > minimaPos )
            {
                long diff = difference( array, minimaPos, pos );
                if ( diff > maxDifference )
                {
                    minimaPosForMaxDifference = minimaPos;
                    maximaPosForMaxDifference = pos;
                    maxDifference   = diff;
                }
            }

        }
        if ( maximaPosForMaxDifference == -1 )
            return null;

        return new int[]{ minimaPosForMaxDifference, maximaPosForMaxDifference };
    }

    public static String toDiffString( final int[] array ){
        final int[] diff = maxDifference( array );
        if ( diff == null )
            return String.format(
                    "%s has no maximum difference",
                    Arrays.toString(array)
            );
        else
            return String.format(
                    "%s has maximum difference of %d at %s",
                    Arrays.toString(array),
                    difference( array, diff[0], diff[1] ),
                    Arrays.toString( diff )
            );
    }
    public static void main( final String[] args ){
        System.out.println( toDiffString( new int[]{} ) );
        System.out.println( toDiffString( new int[]{ 0 } ));
        System.out.println( toDiffString( new int[]{ 0, 0 } ));
        System.out.println( toDiffString( new int[]{ 1, 0 } ));
        System.out.println( toDiffString( new int[]{ 2, 1, 0 } ));
        System.out.println( toDiffString( new int[]{ 0, 1, 2 } ));
        System.out.println( toDiffString( new int[]{2, 3, 10, 2, 4, 8, 1} ));
        System.out.println( toDiffString( new int[]{5,0,3,1,4} ));
        System.out.println( toDiffString( new int[]{5,0,3,-1,4} ));
        System.out.println( toDiffString( new int[]{ Integer.MIN_VALUE, Integer.MAX_VALUE } ));
    }
}

Outputs:

输出：

[] has no maximum difference
[0] has no maximum difference
[0, 0] has maximum difference of 0 at [0, 1]
[1, 0] has no maximum difference
[2, 1, 0] has no maximum difference
[0, 1, 2] has maximum difference of 2 at [0, 2]
[2, 3, 10, 2, 4, 8, 1] has maximum difference of 8 at [0, 2]
[5, 0, 3, 1, 4] has maximum difference of 4 at [1, 4]
[5, 0, 3, -1, 4] has maximum difference of 5 at [3, 4]
[-2147483648, 2147483647] has maximum difference of 4294967295 at [0, 1]

回答by Kostas Chalkias

Just to note that Amit's solution works either working with minimum or maximum. The nice property using maximum is that you only need one extra function (Math.Max). For the unbelievers, just perform a Unit test and check. In any case, this is indeed solvable in O(n).

请注意，Amit的解决方案适用于最小值或最大值。使用最大值的好处是您只需要一个额外的函数 ( Math.Max)。对于不信者，只需执行单元测试和检查。无论如何，这确实可以在 O(n) 中解决。

//using minimum (Amit's solution - vote him up!)
static int maxDifferenceWithMin(int[] a) {
    int minimum, diff = -1;
    if (a.length == 0) {
        return -1;
    }
    minimum = a[0];
    for (int i = 1; i < a.length; i++) {
        diff = Math.max(diff, a[i] - minimum);
        minimum = Math.min(minimum, a[i]);
    }
    return diff;
}

//using maximum
static int maxDifferenceWithMax(int[] a) {
    int maximum, diff = -1;
    if(a.length == 0) {
        return -1;
    }
    maximum = a[a.length - 1];
    for (int i = a.length - 1; i >= 0; i--) {
        diff = Math.max(diff, a[i] - maximum);
        maximum = Math.max(maximum, a[i]);
    }
    return diff;
}

回答by Sanjay Dwivedi

Maximum Difference in an Array

数组中的最大差异

    static int MaxDiff(int[] inputArr)
    {
        int n = inputArr.Length;
        if (n < 1) return -1;
        int max = 0;
        int result = 0;
        int result2 = 0;
        for (int i = 1; i < inputArr.Length-1; i++)
        {
            if (inputArr[i] > inputArr[i - 1])
                max = inputArr[i];
            else
                continue;
            for (int j = i; j > 0; j--)
            {
                result2 = max - inputArr[j - 1];
                if(result2 > result)
                     result = max - inputArr[j - 1];
            }
        }
        return result;
    }

Main Method

主要方法

    static void Main(string[] args)
    {
        int[] inputArr = { 7,2,3,10,2,4,8,1 };
        Console.Write("Maximum Differnce is " + MaxDiff(inputArr));
    }

Output Maximum Differnce is 8

输出最大差为 8

回答by Ankit Pandoh

Old Post but still would like to answer so it may help someone.
Here is my code:

旧帖子，但仍然想回答，所以它可能会帮助某人。
这是我的代码：

    int n = in.readInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
        arr[i] = in.readInt();
    }
    int max = arr[n-1];
    int diff = 0;
    for(int i=n-1;i>=0;i--){
        if(arr[i] > max)
            max = arr[i];
        else{
            diff = Math.max(diff, max-arr[i]);
        }
    }
    out.print(diff);

Logic here is to traverse from right and find maximum number. If number is less than the maximum find the difference (else part). If number is greater than maximum then that will become maximum number(if part). so we are finding difference in a sub array and updating it accordingly.

这里的逻辑是从右遍历并找到最大数。如果数字小于最大值，请找出差异（其他部分）。如果数量大于最大值，那么它将成为最大数量（如果是部分）。所以我们在子数组中找到差异并相应地更新它。