Solutions

# Build a monotonically descreasing stack of (values, index). Pop when the daily temperature is greater than the one at the top of the stack.
# stack

# Stack: O(n) time, O(n) space
def daily_temperatures(temp: list) -> list:
    ans = [0] * len(temp)
    stack = [] # values: (temp, index)

    for i, t in enumerate(temp):
        while stack and stack[-1][0] > t:
            _tmp, idx = stack.pop()
            ans[idx] = i - idx
        stack.append((t, i))
    return ans


# Brute force: O(n^2) time, O(n) space
def daily_temperatures(temp: list) -> list:
    ans = [0] * len(temp)

    for i, t in enumerate(temp):
        j = i + 1
        count = 1
        while j < len(temp):
            if temp[j] > t:
                break
            j += 1
            count += 1
        if j < len(temp):
            ans[i] = count
    return ans