在数组中找到最大差异对 [英] Find the max difference pair in the array

问题描述

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

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

所以情况是:

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

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.

在此示例中:10是最大的元素，1是最小的元素，因为10位于索引2，1位于索引6，所以它不计数，因为较大的货币对指数较低.因此正确的答案是a[0]和a[2]，最大的不同是10-2.

In this example: 10 is the largest element, 1 is the smallest, since 10 is at index 2, 1 is 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.

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

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

我写了这样的代码:

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?

推荐答案

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

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

这篇关于在数组中找到最大差异对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！