找到数组中的最大差异对

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

所以情况是：

给定任何数组，例如这个数组： int[] a = {2, 3, 10, 2, 4, 8, 1} ，找到数组中的最大差值对，同时确保更大的值在指数高于较低值。

在此示例中： 10是最大元素， 1是最小元素，因为10在索引2 ， 1在索引6 ，因此它不计数，因为较大的对处于较低的索引处。 所以正确答案是a[0] ，而a[2] ，最大不同是10-2 。

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

我写了这样的代码：

 static int maxDifference(int[] a) { //test array size if (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; } 

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

令我感到不安的是我只知道有一些我没有通过的测试用例，但没有提示为什么它没有通过。 任何人都可以给我一些建议，以及我在这个辅助方法中可能缺少什么？

Answer 1

基本上你需要跟踪到目前为止找到的最小值和到目前为止找到的最大差异：

 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; } 

Answer 2

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

 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 = a[j] - a[i]; if(difference > biggestDifference){ biggestDifference = difference; } } } return biggestDifference; } 

Answer 3

请注意， Amit的解决方案可以使用最小值或最大值。 使用maximum的nice属性是你只需要一个额外的函数（ Math.Max ）。 对于不信的人，只需执行unit testing并检查。 无论如何，这确实可以在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; } 

Answer 4

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

 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 } )); } } 

输出：

 [] 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] 

Answer 5

数组中的最大差异

  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; } 

主要方法

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

输出最大差异为8

Answer 6

老邮政但仍想回答，这可能对某人有所帮助。
这是我的代码：

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

这里的逻辑是从右边遍历并找到最大数量。 如果number小于最大值，则找到差值（否则为part）。 如果number大于maximum，那么这将成为最大数量（如果是part）。 所以我们在子数组中找到差异并相应地更新它。