Template: 12. MONOTONIC STACK — Next Greater Element

12. MONOTONIC STACK — Next Greater Element

# =============================================================================
def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices
    for i in range(n):
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    return result


# =============================================================================