排序算法 - 查找哪个图表栏看到不同的栏

Question

我很难找到一个具有O(n) runtine效率的算法.

例如,在大小为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(nLogn).它不是一个完整的排序算法,因此可以用O(n)来完成.在运行时打印结果,无需将信息存储到最后.

Answer 1

你可以用一个简单的堆栈来完成它.

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).