找出j和i指标之间的最大差异，使得在O（n）中j> i和a > a
给定一个未sorting的数组，找出max j - i之间的差异，使得在O(n)中j > i和a[j] > a[i] 。 我能够findj和i在O(n^2)复杂性中使用微不足道的方法，但是想知道如何在O(n)做到这一点？
input：{9，2，3，4，5，6，7，8，18，0}
输出：8（j = 8，i = 0）
input：{1，2，3，4，5，6}
输出：5（j = 5，i = 0）
为了简洁起见，我将假设所有元素都是独一无二的。 algorithm可以扩展到处理非唯一元素的情况。
首先，观察如果x和y分别是你想要的最大和最小位置，那么不能有任何a[i] > a[x]和i > x ，同样，没有a[j] < a[y]和j < y 。
所以我们沿数组a扫描并构build一个数组S ，使得S[i]保存a[0:i]最小元素的索引。 类似地，保持a[n-1:i]中的最大元素的索引（即，向后）的数组T
现在我们可以看到， a[S[i]]和a[T[i]]必然是递减序列，因为它们是最小的，直到i和最大的从n到i 。
所以现在我们试着做一个合并类似的过程。 在每一步，如果a[S[head]] < a[T[head]] ，我们从Tpopup一个元素，否则从Spopup一个元素。 在每个这样的步骤中，如果a[S[head]] < a[T[head]] ，则loggingS和T的头部的差异。 最大的这种差异给你你的答案。
编辑：这是一个在Python中实现algorithm的简单代码。
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
我们来做一个简单的观察：如果我们有2个元素a [i]，a [j]和i <j并且a [i] <a [j]，那么我们可以肯定，j不会是解的一部分第一个元素（他可以是第二个，但这是第二个故事），因为我会是一个更好的select。
这告诉我们的是，如果我们贪婪地build立一个递减的序列，那么答案的左边部分肯定会来自那里。
例如：12 3 61 23 51 2贪婪的递减顺序是这样构build的：
12 – > 12 3 – >我们忽略了61，因为它比3更坏 – >我们忽略了23，因为它比3坏 – >我们忽略了51，因为它比3 – > 12 3 2差。
所以答案会包含在左边12 3或2。
现在在一个随机的情况下，这有O（日志N）的长度，所以你可以二进制search每个元素作为答案的正确部分，你会得到O（N日志日志N）这是很好，如果你应用同样的逻辑在string右边的一个随机的情况下可以得到O（log ^ 2 N + N（from the reading）），它是O（N）。 但是我们也可以在非随机情况下做O（N）。
假设我们有这个递减的序列。 我们从string的右边开始，并且执行以下操作，而我们可以将递减序列的最后一个与当前数字配对
1）如果我们find一个更好的解决办法，采取最后的减less序列和当前数量比我们更新答案
2）即使我们更新了答案或不答应，我们popup递减序列的最后一个元素，因为我们是完美匹配的（任何其他匹配都会在左边，并且会给出更小的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索引，使其更清晰，我打印（我，j），而不是（j，我）。 你可以改变它，只要你认为合适。
为了解决这个问题，我们需要得到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 [i]大于RMax [j]，那么在遍历LMin []和RMa []时，我们必须在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, ji); 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; }
我可以想到对O（n ^ 2）的改进，但是在最坏情况下需要validation这是否是O（n）。
- 创build一个variables
BestSoln=0;并遍历第一个元素的数组，并存储第一个元素的bestSoln=k;。- 现在第二个元素只考虑距第二个元素
k距离的元素。- 如果
BestSoln在这种情况下比第一次迭代更好，那么replace它，否则让它是这样的。 继续迭代其他元素。
如果我们为从i开始的每个子数组存储最大元素，则可以进一步改进。 这可以通过从末尾遍历数组在O（n）中完成。 如果一个特定元素超过了本地最大值，那么就不需要对这个元素进行评估。
input：
{9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
为这个数组创build本地最大数组：
[18,18,18,18,18,18,18,0,0] O(n).
现在遍历数组9，这里最好的解决scheme是i=0,j=8 。 现在第二个元素或之后，我们不需要评估。 最好的解决办法是i=0,j=8 。
但是假设数组是Input：
{19, 2, 3, 4, 5, 6, 7, 8, 18, 0,4}
局部最大数组[18,18,18,18,18,18,18,0,0]然后在第一次迭代中，我们不需要评估，因为局部最大值小于当前元素。
现在进行第二次迭代，最好的解决scheme是， i=1,j=10 。 现在对于其他元素，我们不需要考虑评估，因为它们不能给出最好的解决scheme。
让我知道你的看法，我的解决scheme不适用的用例。
这是一个非常简单的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
方法1 （简单但低效）
运行两个循环。 在外部循环中，从左边一个一个地挑选元素。 在内部循环中，将拾取的元素与从右侧开始的元素进行比较。 当你看到一个大于拾取元素的元素时，停止内部循环，并不断更新迄今为止最大的ji。
#include <stdio.h> /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ int maxIndexDiff(int arr[], int n) { int maxDiff = -1; int i, j; for (i = 0; i < n; ++i) { for (j = n-1; j > i; --j) { if(arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } int main() { int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}; int n = sizeof(arr)/sizeof(arr[0]); int maxDiff = maxIndexDiff(arr, n); printf("\n %d", maxDiff); getchar(); return 0; }
时间复杂度：O（n ^ 2）
方法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 [i]大于RMax [j]，那么在遍历LMin []和RMa []时，我们必须在LMin []（或者i ++）中继续前进，因为LMin [i]大于或等于LMin [i]。 否则，我们必须继续在RMax [j]中寻找更大的j-i值。
#include <stdio.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, ji); j = j + 1; } else i = i+1; } return maxDiff; } /* Driver program to test above functions */ int main() { int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}; int n = sizeof(arr)/sizeof(arr[0]); int maxDiff = maxIndexDiff(arr, n); printf("\n %d", maxDiff); getchar(); return 0; }
时间复杂度：O（n）
辅助空间：O（n）
来源geeksforgeeks
这是一个非常简单的解决scheme，用于速度的O（2n）和空间的附加〜O（2n）（除input数组外）。 以下实现在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; }
第一个循环扫描数组一次，为每个元素find剩余元素的最大值。 我们也将相对索引存储在一个单独的数组中。 第二个循环find每个元素和相应的右侧最大值之间的最大值，并返回右侧的索引。
我的解决scheme在O（日志）（请纠正我在这里，如果我错了计算这种复杂性）时间…
想法是插入一个BST，然后search节点，如果该节点有一个正确的孩子，然后遍历右子树来计算具有最大索引的节点..
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; } } } }
Subhasis Das的一个简化algorithm的答案是：
# 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
