maximum i-j，因此A[i]>=A[j]
maximum i-j，因此A[i]>=A[j]
提问于 2017-04-14 04:45:37
让我们假设我们有一个正整数数组A。我们的任务是找到满足以下属性的最大可能i-j，i>j : Ai>=Aj。
举个例子，如果
A[0]=78
A[1]=88
A[2]=64
A[3]=94
A[4]=17
A[5]=91
A[6]=57
A[7]=69
A[8]=38
A[9]=62
A[10]=13
A[11]=17
A[12]=35
A[13]=15
A[14]=20
A[15]=15那么答案是10，因为对于i=14和j=4，Ai>Aj。
哪种算法最适合该任务？
到目前为止，我已经考虑了以下算法:我应用mergesort。我使用一个变量max来存储最终的答案。每当Ai和Aj没有交换时，我检查i-j> max。如果是这样，我会更新max。时间复杂度: O(nlogn)。
有没有更好的算法？
回答 1
Stack Overflow用户
发布于 2017-04-14 05:33:04
对于长度为N的数组，我们可以用O(N)完成此操作。
对于提供最大i-j的i和j，我们必须使A[i]大于所有后续元素，并使A[j]小于所有先前元素。否则，我们可以选择较晚的A[i]或较早的A[j]，从而获得更大的i-j。
查找所有大于所有后续元素的A元素，以及小于所有先前元素的A元素：
j_candidates = [0]
for j in range(1, N):
if A[j] < A[j_candidates[-1]]:
j_candidates.append(j)
i_candidates = [N-1]
for i in reversed(range(N-1)):
if A[i] > A[i_candidates[-1]]:
i_candidates.append(i)
i_candidates.reverse()然后，对于每个j候选者，找到对应的最佳i候选者，从前一个j候选者的最佳i候选者开始搜索。
best_distance = 0
i_candidate_index = 0
for j in j_candidates:
while (i_candidate_index + 1 < len(i_candidates)
and A[j] <= A[i_candidates[i_candidate_index+1]]):
i_candidate_index += 1
best_distance = max(best_distance, i_candidates[i_candidate_index] - j)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43401397
复制相关文章
相似问题
腾讯云开发者
