class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(n)
    where, n is the length of temperatures.
    Monotonic Decreasing Stack approach.
    NOTE: By the way, you can solve this by only storing indices of temperatures in stack.
    For some reason, you previously implement a hashmap along with stack, 
    to keep track of indices, you were storing list of indices for duplicate temperatures, 
    which is over engineering.
    Later, you realized, you could just store tuple of (temperature, index) in stack to keep track of indices, which is simpler and preferred.
    Remember, you can always store extra information in stack elements as tuple or objects.
    Solved in 24 mins, all by yourself! Good job!
    '''
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = deque()
        output = [0] * len(temperatures)
        for i, temp in enumerate(temperatures):
            while stack and temp > stack[-1][0]:
                x = stack.pop()[1]
                output[x] = i-x
            stack.append((temp, i)) # Can also be done, by just storing indices in stack
        return output

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        output = [0] * len(temperatures)
        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                x = stack.pop()
                output[x] = i-x
            stack.append(i)
        return output