Given a sequence of numbers $l_1, \ldots, l_k$, I want to find for each $i$ the nearest numbers to the left and right of $l_i$ (if any) that are strictly smaller than $l_i$. Is it possible to do this in linear time?
Converting my comment into an answer.
Here is an algorithm for the interpretation that you are looking for $l_j$ such that $l_j \lt l_i$ and $|i-j|$ is the smallest.
Traverse left to right, push stuff on stack. If new element to be pushed >= top element. If new element < top element keep popping the stack till top < new element. For the elements popped, the new element is the $l_j$