This problem can be solved efficiently both by parallel and non-parallel algorithms: Berkman, Schieber & Vishkin (1993), who first identified the procedure as a useful subroutine for other parallel programs, developed efficient algorithms to solve it in the Parallel Random Access Machine model; it may also be solved in linear time on a non-parallel computer using a stack-based algorithm.
Berkman, Schieber & Vishkin (1993) mention many other problems that may be solved efficiently in parallel using a nearest smaller values computation.
Among them, they include the following: Similar techniques may also be applied to problems of polygon triangulation, convex hull construction (parallelizing the sequential Graham scan convex hull algorithm), reconstruction of trees from two of the trees' traversal orderings, and quadtree construction.
[2] An even simpler linear-time sequential algorithm (Barbay, Fischer & Navarro (2012), Lemma 1) does not even need a stack; it assumes that the input sequence is given as an array A[1,n] of size n, and stores the index j of the preceding smaller value of the ith value A[i] in P[i].
We assume an artificial overall minimum at A[0]: Berkman, Schieber & Vishkin (1993) showed how to solve the all nearest smaller values problem efficiently on a concurrent-read concurrent-write Parallel Random Access Machine.