# Python3

class Solution:
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """

        # approach: use a stack for saving decreasing temperatures
        #           and update their distance once there is a
        #           temperature is greater than top of stack

        n = len(temperatures)
        stack = []
        result = [0] * n

        for i in range(n):
            current_temperature = temperatures[i]

            # pop all temperatures in stack out and update indices
            while len(stack) and current_temperature > temperatures[stack[-1]]:
                item_index = stack.pop()
                result[item_index] = i - item_index

            stack.append(i)

        return result