分享｜【算法题单】单调栈（矩形面积/贡献法/最小字典序）

# 返回 left，其中 left[i] 是 nums[i] 左侧最近的严格大于 nums[i] 的数的下标，若不存在则为 -1
# 时间复杂度 O(len(nums))
def left_greater(nums: list[int]) -> list[int]:
    n = len(nums)
    left = [-1] * n
    st = []
    for i, x in enumerate(nums):
        while st and nums[st[-1]] <= x:  # 如果求严格小于，改成 >=
            st.pop()
        if st:
            left[i] = st[-1]
        st.append(i)
    return left

# 返回 right，其中 right[i] 是 nums[i] 右侧最近的严格大于 nums[i] 的数的下标，若不存在则为 len(nums)
# 时间复杂度 O(len(nums))
def right_greater(nums: list[int]) -> list[int]:
    n = len(nums)
    right = [n] * n
    st = []
    for i in range(n - 1, -1, -1):
        x = nums[i]
        while st and nums[st[-1]] <= x:  # 如果求严格小于，改成 >=
            st.pop()
        if st:
            right[i] = st[-1]
        st.append(i)
    return right