Monotonic Stack

def next_greater_element(nums):
    """For each element, find the next element that is greater."""
    n = len(nums)
    result = [-1] * n
    stack = []  # stores INDICES, maintains decreasing values

    for i in range(n):
        # Pop all smaller elements — current is their "next greater"
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

# nums =   [2, 1, 2, 4, 3]
# result = [4, 2, 4,-1,-1]   (traced step by step in the visualizer above)

def next_smaller_element(nums):
    """For each element, find the next element that is smaller."""
    n = len(nums)
    result = [-1] * n
    stack = []  # stores INDICES, maintains increasing values

    for i in range(n):
        while stack and nums[stack[-1]] > nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

def dailyTemperatures(temperatures):
    """Days until a warmer temperature. Classic next greater element."""
    n = len(temperatures)
    result = [0] * n
    stack = []  # decreasing stack of indices

    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            idx = stack.pop()
            result[idx] = i - idx  # distance, not value
        stack.append(i)

    return result

# temps =   [73, 74, 75, 71, 69, 72, 76, 73]
# result =  [ 1,  1,  4,  2,  1,  1,  0,  0]
#
# i=0 (73): stack=[0]
# i=1 (74): 74>73 → pop 0, result[0]=1-0=1     stack=[1]
# i=2 (75): 75>74 → pop 1, result[1]=2-1=1     stack=[2]
# i=3 (71): 71<75                                stack=[2,3]
# i=4 (69): 69<71                                stack=[2,3,4]
# i=5 (72): 72>69 → pop 4, result[4]=5-4=1
#           72>71 → pop 3, result[3]=5-3=2      stack=[2,5]
# i=6 (76): 76>72 → pop 5, result[5]=6-5=1
#           76>75 → pop 2, result[2]=6-2=4      stack=[6]
# i=7 (73): 73<76                                stack=[6,7]
# Remaining: result[6]=0, result[7]=0

def nextGreaterElements(nums):
    """Circular array: treat as if array is doubled."""
    n = len(nums)
    result = [-1] * n
    stack = []

    # Iterate through array TWICE (simulate circular)
    for i in range(2 * n):
        idx = i % n
        while stack and nums[stack[-1]] < nums[idx]:
            result[stack.pop()] = nums[idx]
        if i < n:  # only push indices from first pass
            stack.append(i)

    return result

# nums = [1, 2, 1]  →  conceptually [1, 2, 1, | 1, 2, 1]
# First pass:  normal next greater
# Second pass: wrap around to find answers for remaining
# result = [2, -1, 2]   (1→2, 2→none since it's the max, 1→2 wrapping)

def largestRectangleArea(heights):
    """Find the largest rectangle that fits under the histogram."""
    stack = []  # increasing stack of indices
    max_area = 0
    heights.append(0)  # sentinel to flush remaining bars

    for i in range(len(heights)):
        while stack and heights[stack[-1]] > heights[i]:
            h = heights[stack.pop()]
            # Width: from current i to the new stack top
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)

    heights.pop()  # restore input
    return max_area

# heights = [2, 1, 5, 6, 2, 3]
#
# i=0(2): push          stack=[0]
# i=1(1): pop 0, h=2, w=1, area=2    stack=[1]
# i=2(5): push          stack=[1,2]
# i=3(6): push          stack=[1,2,3]
# i=4(2): pop 3, h=6, w=4-2-1=1, area=6
#         pop 2, h=5, w=4-1-1=2, area=10  ← MAX
#         push           stack=[1,4]
# i=5(3): push          stack=[1,4,5]
# sentinel(0): pop 5, h=3, w=6-4-1=1, area=3
#              pop 4, h=2, w=6-1-1=4, area=8
#              pop 1, h=1, w=6, area=6
#
# Answer: 10 (bar of height 5, width 2)

def removeKdigits(num, k):
    """Remove k digits to make the smallest possible number."""
    stack = []  # increasing stack (build smallest number)

    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # If k removals remain, remove from the end
    stack = stack[:len(stack) - k]

    # Remove leading zeros and handle empty result
    return "".join(stack).lstrip("0") or "0"

# num = "1432219", k = 3
#
# '1': stack=[1]
# '4': stack=[1,4]
# '3': 3<4, pop 4 (k=2), stack=[1,3]
# '2': 2<3, pop 3 (k=1), stack=[1,2]
# '2': stack=[1,2,2]
# '1': 1<2, pop 2 (k=0), stack=[1,2,1]
# '9': stack=[1,2,1,9]
#
# k=0, done. Result: "1219"

def trap(height):
    """Calculate trapped rainwater using a monotonic stack."""
    stack = []  # decreasing stack of indices
    water = 0

    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = height[stack.pop()]
            if not stack:
                break
            # Water trapped between stack[-1] and i, above bottom
            w = i - stack[-1] - 1
            h = min(height[stack[-1]], height[i]) - bottom
            water += w * h
        stack.append(i)

    return water

def stock_span(prices):
    """For each day, how many consecutive days price was <= today's price."""
    n = len(prices)
    span = [0] * n
    stack = []  # decreasing stack of indices

    for i in range(n):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        # Span = distance to previous greater element (or start)
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)

    return span

# prices = [100, 80, 60, 70, 60, 75, 85]
# span   = [  1,  1,  1,  2,  1,  4,  6]
#
# Day 5 (75): previous greater is day 1 (80), span = 5-1 = 4
# Day 6 (85): previous greater is day 0 (100), span = 6-0 = 6