I'm required to perform the following operation on an array in O(n): P[1..n] is an array of positive integers. For each index 'i' in the array, I must find how many "cells" I can advance toward the beginning of the array until I reach an element whose value is greater than P[i], or reach the beginning of the array. The output of the function should be an array S[1..n] that contains these values.
For example, if:
P = [ 4, 3, 6, 1, 2, 7, 9 ]
Then I must create this array:
S = [ 1, 1, 3, 1, 2, 6, 7 ]
If I start at P (=6), I can advance 3 cells until the beginning of the array, and therefore S = 3; but if I start at P (=2) I will advance only 2 cells and reach P (=6 > 2), so S = 2.
Implementing such algorithm in O(n^2) is trivial, but I'm required to do so in O(n). I was hinted to use a stack.