我很难找到一个具有O(n)运行库效率的算法。
例如，如果数组大小为n，则数组包含整数。我必须知道哪个数组单元格(可以想象为图表栏)正在查看哪个单元格。
形式上：lookingAtIndex(i) = max { -1} U {j | arr[j] > arr[i], j<i}，其中-1代表y轴。
编辑：比当前栏高的第一个栏是什么。如果没有，它的Y轴示例，提供阵列：7,3,5,2,1,9.
然后7在y轴上看，3在7上看，5在7上，2在5上，1在2上，9在y轴。
我有点迷路了，我做的每件事都留在O(登录)。这不是一个完整的排序算法，因此可以用O(n)来完成。打印结果在运行时是可能的，不需要存储信息直到结束。
您可以用一个简单的堆栈来完成。
Compare each element a[i] with the top of the stack T
while ( T <= a[i] )
pop T
if the stack is empty
a[i] is looking at the y-axis
else
a[i] is looking at T
push a[i] onto the stack
例如，使用数组[7,3,5,2,1,9]
a[0]=7 T=empty 7 is looking at y-axis
a[1]=3 T=7 3 is looking at 7
a[2]=5 T=3 pop 3
T=7 5 is looking at 7
a[3]=2 T=5 2 is looking at 5
a[4]=1 T=2 1 is looking at 2
a[5]=9 T=1 pop 1
T=2 pop 2
T=5 pop 5
T=7 pop 7
T=empty 9 is looking at y-axis
注意，每个数字都被推送到堆栈上，每个数字只能从堆栈中弹出一次，因此堆栈操作的次数最多为2N，整个算法为O(n)。
我提出了一个线性解，前面有一个很大的因子。所以我认为这可能不是最好的解决方案。
事情是这样的。让我们调用长度为n的整数的输入数组I。设M是I中的最大数，在O(n)中找到。我首先假设I中的最小值是0；如果不是，减去最小值不会改变解，并且M在一般情况下是max(I)-min(I)。
创建一个长度为m的数组T，所有元素都设置为-1。这个数组是I中每个可能的整数的"查看"条的索引的存储；初始化为-1，虚拟最左边栏的索引。
还创建数组S，该数组是"查看"条的索引的输出数组。
现在，对于数组中索引为i的I中的每个元素e，它会查看索引正是T[e]的条。所以S[i] = T[e]。然后用值CCD_ 21设置所有元素CCD_。
在循环结束时，S填充有"查看"条的索引；很容易收回这些酒吧的价值。
正如你所看到的，总体复杂度是O(M*n)，所以复杂度与I的长度是线性的。正如我之前所说，由于因子M，它可能不是很有效(欢迎任何改进)。
编辑
更喜欢用户3386109的解决方案，相比之下，我的解决方案很尴尬。
假设我们有一个数组，其结尾为：。。。A-B，
和lookingAtIndex(A)=X，让我们找到B的结果：如果A>B，那么它是A，否则A和lookingAtIndex(A)之间的所有索引都不可能是一个好的答案，因为它们小于A，如果lookingAtIndex(A)>B，那么它就是答案，否则就看lookingAtIndex(lookingAtIndex(A))等等…
但是你需要一种方法来存储每个索引的条，我认为user3386109给出的堆栈的想法是一个非常好的实现，你只需要存储所需的值