47

並べ替えられていない配列が与えられた場合、そのようなインデックスとinのmax j - i違いを見つけます。単純な方法を複雑に見つけて使用することはできますが、これを行う方法を知りたいですか?j > ia[j] > a[i]O(n)jiO(n^2)O(n)

入力: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

出力: 8 (j = 8、i = 0)

入力: {1, 2, 3, 4, 5, 6}

出力: 5 (j = 5、i = 0)

4

15 に答える 15

40

簡潔にするために、すべての要素が一意であると仮定します。このアルゴリズムは、一意でない要素のケースを処理するように拡張できます。

最初に、 と がそれぞれ目的の最大位置と最小位置である場合x、 とyは存在できずa[i] > a[x]、i > x同様に と も存在しないことに注意a[j] < a[y]してj < yください。

そのため、配列に沿ってスキャンし、 の最小要素のインデックスを保持するような配列aを構築します。同様に、最大要素のインデックスを保持する配列(つまり、後方)。SS[i]a[0:i]Ta[n-1:i]

a[S[i]]これで、とa[T[i]]が必然的に減少するシーケンスであることがわかります。これは、それぞれが最小までiと最大からnまでであったためiです。

そこで、マージソートのような手順を実行しようとしています。各ステップで、 の場合a[S[head]] < a[T[head]]は から要素をT取り出し、それ以外の場合は から要素を取り出しSます。そのような各ステップで、 S と T if の頭の違いを記録しa[S[head]] < a[T[head]]ます。そのような最大の差があなたの答えになります。

編集: これは、アルゴリズムを実装する Python の簡単なコードです。

def getMaxDist(arr):

    # get minima going forward
    minimum = float("inf")
    minima = collections.deque()
    for i in range(len(arr)):
        if arr[i] < minimum:
            minimum = arr[i]
            minima.append((arr[i], i))

    # get maxima going back
    maximum = float("-inf")
    maxima = collections.deque()
    for i in range(len(arr)-1,0,-1):
        if arr[i] > maximum:
            maximum = arr[i]
            maxima.appendleft((arr[i], i))

    # do merge between maxima and minima
    maxdist = 0
    while len(maxima) and len(minima):
        if maxima[0][0] > minima[0][0]:
            if maxima[0][1] - minima[0][1] > maxdist:
                maxdist = maxima[0][1] - minima[0][1]
            maxima.popleft()
        else:
            minima.popleft()

    return maxdist
于 2013-08-16T21:14:21.743 に答える
0

これは、O(2n) の速度と追加の ~O(2n) のスペース (入力配列に加えて) に対する非常に単純なソリューションです。次の実装は C です。

int findMaxDiff(int array[], int size) {

    int index = 0;
    int maxima[size];
    int indexes[size];

    while (index < size) {
        int max = array[index];
        int i;
        for (i = index; i < size; i++) {
            if (array[i] > max) {
                max = array[i];
                indexes[index] = i;
            }
        }
        maxima[index] = max;
        index++;
    }

    int j;
    int result;
    for (j = 0; j < size; j++) {
        int max2 = 0;
        if (maxima[j] - array[j] > max2) {
            max2 = maxima[j] - array[j];
            result = indexes[j];
        }
    }

    return result;
}

最初のループは、配列を 1 回スキャンし、各要素の右側にある残りの要素の最大値を見つけます。相対インデックスも別の配列に格納します。2 番目のループは、各要素と対応する右側の最大値の間の最大値を見つけ、右側のインデックスを返します。

于 2013-08-26T16:22:41.773 に答える
0

int maxIndexDiff(int arr[], int n) {

    // Your code here
    vector<int> rightMax(n);
    rightMax[n-1] = arr[n-1];
    for(int i =n-2;i>=0;i--){
        rightMax[i] = max(rightMax[i+1],arr[i]); 
    }
    int i = 0,j=0,maxDis = 0;
    while(i<n &&j<n){
        if(rightMax[j]>=arr[i]){
            maxDis = max(maxDis,j-i);
            j++;
        } else
            i++;
    }
    return maxDis;
}

leftMin と rightMax を保持するという概念がありますが、leftMin は実際には必要なく、とにかく leftMin が機能します。rightMax を選択し、それよりも小さい値が得られるまで最初からトラバースします。

于 2021-07-16T21:35:50.117 に答える
0

このソリューションと、失敗する可能性のあるケースを確認してください。

def maxIndexDiff(arr, n):
    j = n-1
    for i in range(0,n):
        if j > i:
            if arr[j] >= arr[i]:
                return j-i
            elif arr[j-1] >= arr[i]:
                return (j-1) - i
            elif arr[j] >= arr[i+1]:
                return j - (i+1)
        j -= 1
    return -1
于 2019-09-15T23:31:45.310 に答える