如何找到数组的 i 和 j indeces，其中 A[j] - A[i] 是最大值，i < j？

Question

我已经找到了很多解决这个问题的方法，但是时间复杂度是O(n^2)。我要找到时间复杂度为0 (n)的解。我在那里看到的解决方案:https://www.geeksforgeeks.org/maximum-difference-between-two-elements/工作得很好，但如何得到数字索引，不使它更复杂?谢谢你的回答!

Answer 1

我相信这行得通:

• 迭代数组，跟踪到目前为止最小值的索引(O(n))
  • 为每个索引插入一个表项到map中:currMinIdx
  • 使用当前值更新当前值
• 你现在有一个与每个索引相关联的最小值索引的地图
• 迭代该映射并确定最大差值(O(n))
在伪代码:

//init variables
int currMinIdx = -1
map<Int, Int> maxIdxToMinIdxMap // a map of the index of the min value for a given index
//iterate the array to populate the map
for every i in A:    
maxToMinIdxMap[i] = currMinIdx
if A[i] < A[currMinIdx]:
currMinIdx = i

int currMinIdx2 = -1
int currMaxIdx2 = -1
int currMaxDiff
for every entry in maxIdxToMinIdxMap:
if A[entry.key] - A[entry.value] > currMaxDiff:
currMaxDiff = A[entry.key] - A[entry.value]
currMaxIdx2 = entry.key
currMinIdx2 = entry.value