Monotonic Stacks

MonotonicStack.py

nums = [1,4,3,2,2,1,9]
        
m = len(nums)

# Next Smallest
next_smallest = [-1] * m
stack = []
for i in range(m):
    if stack:
        while stack and stack[-1][1] > nums[i]:
            idx, num = stack.pop()
            next_smallest[idx] = nums[i]
    stack.append((i,nums[i]))

# Next Largest
next_largest = [-1] * m
stack = []
for i in range(m):
    if stack:
        while stack and stack[-1][1] < nums[i]:
            idx, num = stack.pop()
            next_largest[idx] = nums[i]
    stack.append((i,nums[i]))

# Next Smaller
next_smaller = [-1] * m
stack = []
for i in range(m):
    if stack:
        while stack and stack[-1][1] > nums[i]:
            idx, num = stack.pop()
            next_smaller[idx] = nums[i]
            break
    stack.append((i,nums[i]))

# Next Larger
next_larger = [-1] * m
stack = []
for i in range(m):
    if stack:
        while stack and stack[-1][1] < nums[i]:
            idx, num = stack.pop()
            next_larger[idx] = nums[i]
            break
    stack.append((i,nums[i]))

print("Original: \t\t{}".format(nums))
print("Next Smallest: \t{}".format(next_smallest))
print("Next Largest: \t{}".format(next_largest))
print("Next Smaller: \t{}".format(next_smaller))
print("Next Larger: \t{}".format(next_larger))

"""
Original:       [1, 4, 3, 2, 2, 1, 9]
Next Smallest: 	[-1, 3, 2, 1, 1, -1, -1]
Next Largest: 	[4, 9, 9, 9, 9, 9, -1]
Next Smaller: 	[-1, 3, 2, -1, 1, -1, -1]
Next Larger: 	[4, -1, -1, -1, -1, 9, -1]
"""