stack = []res = []for item in collection: while stack and stack[-1] >= item: # pop recent items that is larger than the current one stack.pop() if stack: # this is the nearest smaller item (to the left) res.append(stack[-1]) else: # there is no such item res.append(None) stack.append(item)
Properties
The stack is sorted in the ascending order for finding the nearest smaller values.
Hence, Binary Search can be applied on the stack to quickly retrieve the value satisfying a condition.