monotonic_stack.md

Monotonic Stack

• A monotonic stack is a special form stack inside which all elements are sorted in either ascending or descending order

Template

def monotonic_stack(nums):
    """An increasing monotonic stack, all elements are sorted in ascending order"""

    stack = []
    res = [-1] * len(nums)

    # Template for descending traversal
    for i in range(len(nums)-1, -1, -1):
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()   # Remove existing element that is smaller than incoming element
        if stack:
            res[i] = nums[stack[-1]]
        stack.append(i)  # use for next iteration

    # # Template for ascending traversal
    # for i in range(len(nums)):
    #     while stack and (nums[stack[-1]] < nums[i]):
    #         res[stack.pop()] = nums[i]
    #     stack.append(i)
    return res

Reference:

• Using monotonic stack w/ analysis

Practice:

• 496. Next Greater Element I
• 503. Next Greater Element II
• 739. Daily Temperatures
• 1019. Next Greater Node In Linked List
• 316. Remove Duplicate Letters
• 402. Remove K Digits
• 42. Trapping Rain Water
• 84. Largest Rectangle in Histogram