# [Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)
###### tags: `Leetcode`, `Stack`, `Medium`

## Approach

* Follow an approach using a Monotonic Decreasing Stack
* Initialize a stack with default values as 0. Length of stack will be equal to the length of input list
* Initialize an output list
* For every element in the input list:
* If stack is empty or element is less than the top element of stack, then just add this element to the stack
* If stack is not empty and the element is greater than the top element of stack then pop the top element and to the output list at the index of the popped element, add `index_of_current_element - index_of_popped_element`
* Return output

## Asymptotic Analysis
### Time Complexity: **O(N)**
### Space Complexity: **O(N)**

## Code

from typing import List


class DailyTemperatures:
    def daily_temperatures(self, temperatures: List[int]) -> List[int]:
        stack, output = [], [0] * len(temperatures)
        for index, temp in enumerate(temperatures):
            if not stack:
                stack.append((temp, index))
            while stack and temp > stack[-1][0]:
                removed_element = stack.pop()
                r_temp, r_index = removed_element[0], removed_element[1]
                output[r_index] = index - r_index
            stack.append((temp, index))
        return output


temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(DailyTemperatures().daily_temperatures(temps))