Nearest smaller value search finds the closest preceding element with a smaller value for each input element. For (8 11 4 12 5 6), it returns (8 4 4 5): the first element has no result, while each later element uses its nearest qualifying predecessor. section 9.4.1
A stack makes the search efficient. When the stack top is not smaller than the current value, pop it and continue; otherwise, emit the top and push the current value. Each item is pushed and popped at most once, limiting the nested loop to a constant factor per item. section 9.4.1
Lazy Clojure implementation
The implementation combines a list-backed stack with peek, pop, conj, loop, and lazy-seq. (nearest-smaller [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15]) produces (0 0 4 0 2 2 6 0 1 1 5 1 3 3 7).
