在 O(n) 时间复杂度内找到 j 和 i 索引之间的最大差值，使得 j > i 且 a[j] > a[i]。

Question

在 O(n) 时间复杂度内找到 j 和 i 索引之间的最大差值，使得 j > i 且 a[j] > a[i]。

47

给定一个未排序的数组，找到满足条件 j > i 且 a[j] > a[i] 的下标 i 和 j之间的最大差值 j - i，并在 O(n) 时间复杂度内解决。我可以使用简单的方法在 O(n^2) 复杂度内找到 j 和 i，但我想知道如何在 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)

- manav m-n

4

我可以想到两种O(NlogN)的方法来实现它。需要思考一段时间才能确定是否可能用O(N)的方法实现。 - WhozCraig

3

如果数组按降序排序会发生什么？没有解决方案吗？ - liori

1

жҲ‘дёҚжҳҺзҷҪжҺ’еәҸгҖҒдәҢеҲҶжҹҘжүҫжҲ–д»»дҪ•е…·жңүlg Nеӣ еӯҗзҡ„з®—жі•дёҺи§ЈеҶіж–№жЎҲжңүд»Җд№Ҳе…ізі»пјҹиҜҘж•°з»„жҳҜжңӘжҺ’еәҸзҡ„гҖӮй—®йўҳиҰҒжұӮеңЁе…¶дёӯжүҫеҲ°дёӨдёӘе…ғзҙ пјҢе®ғд»¬д№Ӣй—ҙзҡ„и·қзҰ»жңҖиҝңпјҢе№¶ж»Ўи¶ідёҖдёӘдёҚзӯүејҸгҖӮ - Happy Green Kid Naps

14

这被称为“股票市场问题”，是本科算法课程中相当标准的作业任务。 - Phil Miller

1

@PhilMiller 你是在谈论问题吗？ - rainyday

显示剩余18条评论

15个回答

4

让我们做个简单的观察：如果我们有两个元素a[i]和a[j]，其中i < j且a[i] < a[j]，那么我们可以确定j不会成为解的第一个元素（他可能成为第二个，但那是另外一回事），因为i是更好的替代者。

这告诉我们，如果我们从a的元素中贪心地构建一个递减序列，左半部分的答案肯定来自于那里。

例如，对于：12 3 61 23 51 2，贪婪的递减序列如下所示：

12 -> 12 3 -> 我们忽略61，因为它比3差-> 我们忽略23，因为它比3差-> 我们忽略51，因为它比3差-> 12 3 2。

因此，答案左侧将包含12 3或2。

现在，在随机情况下，它的长度为O(log N)，因此您可以针对每个元素进行二进制搜索，作为答案的右侧，这将得到O(N log log N)，这很不错，如果您在字符串的右侧应用相同的逻辑，则在随机情况下，您可以获得O(log^2 N + N(从读取))，这是O(N)。但是，在非随机情况下，我们也可以做到O(N)。

假设我们有这个递减序列。我们从字符串的右侧开始，做以下操作，只要我们可以将递减序列的最后一个与当前数字配对：

1）如果通过取递减序列的最后一个和当前的数字找到更好的解，则更新答案

2）即使我们更新了答案，或者没有更新答案，我们也会弹出递减序列的最后一个元素，因为我们是它的完美匹配（任何其他匹配都在左侧，并且会给出具有更小j-i的答案）

3）重复，直到我们可以配对这两个对象

示例代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N; cin >> N;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> A[i];

    // let's solve the problem
    vector<int> decreasing; 

    pair<int, int> answer;

    // build the decreasing sequence
    decreasing.push_back(1);
    for (int i = 1; i <= N; ++i)
        if (A[i] < A[decreasing.back()])
            decreasing.push_back(i); // we work with indexes because we might have equal values

    for (int i = N; i > 0; --i) {
        while (decreasing.size() and A[decreasing.back()] < A[i]) { // while we can pair these 2
            pair<int, int> current_pair(decreasing.back(), i);
            if (current_pair.second - current_pair.first > answer.second - answer.first)
                answer = current_pair;
            decreasing.pop_back();
        }
    }

    cout << "Best pair found: (" << answer.first << ", " << answer.second << ") with values (" << A[answer.first] << ", " << A[answer.second] << ")\n";
}

稍后编辑：我看到您举了一个例子：我从1开始索引，以使它更清晰，并打印(i，j)而不是(j，i)。您可以根据需要进行修改。

- adrian.budau

2

假设我们有这个递减的序列。您之后的话无法理解。 - windchime

3

我们可以避免检查整个数组，而是从最大差值的j-i开始，并为该特定最大差值的所有可能组合j和i比较arr[j]>arr[i] 每当我们得到一个带有(j,i)的组合和arr[j]>arr[i]时，我们可以退出循环。

例如：在数组{2,3,4,5,8,1}中，第一个代码将检查最大差值5(5-0)即(arr[0],arr[5])，如果arr[5]>arr[0]则函数将退出，否则将取最大差值4的组合(5,1)和(4,0)，即arr[5]、arr[1]和arr[4]、arr[0]

int maxIndexDiff(int arr[], int n)
{
    int maxDiff = n-1;
    int i, j;

    while (maxDiff>0)
    {
        j=n-1;
        while(j>=maxDiff)
        {
            i=j - maxDiff;
            if(arr[j]>arr[i])
            { 
                return maxDiff;  
            }
            j=j-1;
        }
        maxDiff=maxDiff-1;
    }
    return -1;  
}`

https://ide.geeksforgeeks.org/cjCW3wXjcj

- Anish Antony

2

这是一个非常简单的O(n) Python实现，采用了合并下降序列的思想。即使存在重复值，该实现也可以正常工作：

downs = [0]
for i in range(N):
    if ar[i] < ar[downs[-1]]:
        downs.append(i)

best = 0
i, j = len(downs)-1, N-1
while i >= 0:
    if ar[downs[i]] <= ar[j]:
        best = max(best, j-downs[i])
        i -= 1
    else:
        j -= 1
print best

- Thomas Ahle

2

为了解决这个问题，我们需要得到arr[]的两个最优索引：左索引i和右索引j。对于一个元素arr[i]，如果在arr[i]的左侧存在比arr[i]小的元素，则我们不需要考虑arr[i]作为左索引。同样地，如果在arr[j]的右侧存在更大的元素，则我们不需要考虑此j作为右索引。因此，我们构造两个辅助数组LMin[]和RMax[]，其中LMin[i]保存包括arr[i]在内的arr[i]左侧的最小元素，而RMax[j]保存包括arr[j]在内的arr[j]右侧的最大元素。构造这两个辅助数组后，我们从左到右遍历这两个数组。在遍历LMin[]和RMax[]时，如果我们发现LMin[i]大于RMax[j]，那么我们必须在LMin[]中向前移动（或执行i++），因为在LMin[i]左侧的所有元素都大于或等于LMin[i]。否则，我们必须在RMax[j]中向前移动，以寻找更大的j-i值。以下是运行时间为O(n)的C代码：

#include <stdio.h>
#include <stdlib.h>

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}

int min(int x, int y)
{
    return x < y? x : y;
}

/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;

    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);

   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);

    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);

    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }

    return maxDiff;
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}

- jfly

1

使用辅助数组的 Subhasis Das 答案的简化版本。

def maxdistance(nums):
    n = len(nums)
    minima ,maxima = [None]*n, [None]*n
    minima[0],maxima[n-1] = nums[0],nums[n-1]
    for i in range(1,n):
        minima[i] = min(nums[i],minima[i-1])
    for i in range(n-2,-1,-1):
        maxima[i]= max(nums[i],maxima[i+1])

    i,j,maxdist = 0,0,-1
    while(i<n and j<n):
        if minima[i] <maxima[j]:
            maxdist = max(j-i,maxdist)
            j = j+1
        else:
            i += 1
    print maxdist

- Majnu

0

我的解决方案在O(log n)时间内完成（如果我在计算这个复杂度时出错，请纠正我）...

思路是将节点插入二叉搜索树，然后搜索节点，如果该节点有右子节点，则遍历右子树以计算具有最大索引的节点。

    import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{

    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t1 = Integer.parseInt(br.readLine());
        for(int j=0;j<t1;j++){
            int size = Integer.parseInt(br.readLine());
            String input = br.readLine();
            String[] t = input.split(" ");
            Node root = new Node(Integer.parseInt(t[0]),0);
            for(int i=1;i<size;i++){
                Node addNode = new Node(Integer.parseInt(t[i]),i);
                insertIntoBST(root,addNode);                
            }
            for(String s: t){
                Node nd = findNode(root,Integer.parseInt(s));
                if(nd.right != null){
                    int i = nd.index;
                    int j1 = calculate(nd.right);
                    mVal = max(mVal,j1-i);
                }

            }

            System.out.println(mVal);
            mVal=0;
        }
    }

    static int mVal =0;

    public static int calculate (Node root){
        if(root==null){
            return -1;
        }
        int i = max(calculate(root.left),calculate(root.right));
        return max(root.index,i);
    }

    public static Node findNode(Node root,int n){
        if(root==null){
            return null;
        }
        if(root.value == n){
            return root;
        }
        Node result = findNode(root.left,n);
        if(result ==null){
            result = findNode(root.right,n);   
        }
        return result;
    }

    public static int max(int a , int b){
        return a<b?b:a;
    }

    public static class Node{
        Node left;
        Node right;
        int value;
        int index;

        public Node(int value,int index){
            this.value = value;
            this.index = index;
        }
    }

    public static void insertIntoBST(Node root, Node addNode){

        if(root.value< addNode.value){
            if(root.right!=null){
                insertIntoBST(root.right,addNode);              
            }else{
                root.right = addNode;
            }
        }
        if(root.value>=addNode.value){
            if(root.left!=null){
                insertIntoBST(root.left,addNode);               
            }else{
                root.left =addNode;
            }
        }
    }


}

- Sumeet Sharma

1

你必须至少访问每个数组元素一次，因此最佳解决方案应该需要 Ω(N) 的时间。同时请注意，BST 不会自动给出 log N，它应该是一个自平衡的树。 - Evg

0

创建键为数组元素，值为索引的Pair（一种数据结构）ArrayList。对这个Pair ArrayList 进行排序。遍历这个Pair ArrayList来获取最大间隔(maxj-i)，同时跟踪maxj并在找到新的maxj时进行更新。以下是我的Java解决方案，其时间复杂度为O(nlogn)，空间复杂度为O(n)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class MaxDistanceSolution {
    private class Pair implements Comparable<Pair> {
        int key;
        int value;

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(Pair o) {
            return this.getKey() - o.getKey();
        }
    }

    public int maximumGap(final ArrayList<Integer> A) {
        int n = A.size();
        ArrayList<Pair> B = new ArrayList<>();
        for (int i = 0 ; i < n; i++)
            B.add(new Pair(A.get(i), i));
        Collections.sort(B);
        int maxJ = B.get(n-1).getValue();
        int gaps = 0;
        for (int i = n - 2; i >= 0; i--) {
            gaps = Math.max(gaps, maxJ - B.get(i).getValue());
            maxJ = Math.max(maxJ, B.get(i).getValue());
        }
        return gaps;
    }
}

public class MaxDistance {
    public static void main(String[] args) {
        MaxDistanceSolution sol = new MaxDistanceSolution();
        ArrayList<Integer> A = new ArrayList<>(Arrays.asList(3, 5, 4, 2));
        int gaps = sol.maximumGap(A);
        System.out.println(gaps);
    }
}

- Tejas Morajkar

0

以下是针对条件 a[i] <= a[j] 的 C++ 解决方案。它需要进行轻微修改以处理情况 a[i] < a[j]。

template<typename T>
std::size_t max_dist_sorted_pair(const std::vector<T>& seq)
{
    const auto n = seq.size();
    const auto less = [&seq](std::size_t i, std::size_t j)
        { return seq[i] < seq[j]; };

    // max_right[i] is the position of the rightmost
    // largest element in the suffix seq[i..]
    std::vector<std::size_t> max_right(n);

    max_right.back() = n - 1;
    for (auto i = n - 1; i > 0; --i)
        max_right[i - 1] = std::max(max_right[i], i - 1, less);

    std::size_t max_dist = 0;
    for (std::size_t i = 0, j = 0; i < n; ++i)
        while (!less(max_right[j], i))
        {
            j = max_right[j];
            max_dist = std::max(max_dist, j - i);
            if (++j == n)
                return max_dist;
        }

    return max_dist;
}

- Evg

0

从Subhasis Das的答案中简化的算法：

# assume list is not empty
max_dist = 0
acceptable_min = (0, arr[0])
acceptable_max = (0, arr[0])
min = (0, arr[0])

for i in range(len(arr)):
  if arr[i] < min[1]:
    min = (i, arr[i])
  elif arr[i] - min[1] > max_dist:
    max_dist = arr[i] - min[1]
    acceptable_min = min
    acceptable_max = (i, arr[i])

# acceptable_min[0] is the i
# acceptable_max[0] is the j
# max_dist is the max difference

- Chenxi Yuan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Subhasis Das · Accepted Answer

为了简洁起见，我假设所有元素都是独一无二的。该算法可以扩展到处理非唯一元素的情况。

首先，观察如果 x 和 y 是您所需的最大和最小位置，那么就不可能存在 a[i] > a[x] 且 i > x，同样的，也不存在 a[j] < a[y] 且 j < y。

因此我们沿着数组 a 扫描并构建一个数组 S，其中 S[i] 存储在 a[0:i] 中的最小元素的索引。类似地，构建一个数组 T，它在 a[n-1:i] （即反向）中存储最大元素的索引。

现在我们可以看到 a[S[i]] 和 a[T[i]] 必定是递减的序列，因为它们分别是从 i 之前的最小值和从 n 至 i 的最大值。

因此，我们现在尝试执行类似于归并排序的过程。在每个步骤中，如果 a[S[head]] < a[T[head]]，我们从 T 中弹出一个元素，否则我们从 S 中弹出一个元素。在每个这样的步骤中，如果 a[S[head]] < a[T[head]]，我们记录 S 和 T 头部之间的差异。最大的这种差异就是您要找到的答案。

编辑：这里是使用 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