# LC 739. Daily Temperatures

### [Problem link](https://leetcode.com/problems/daily-temperatures/)

###### tags: `leedcode` `python` `c++` `medium` `Monotone Stack`

Given an array of integers <code>temperatures</code> represents the daily temperatures, return an array <code>answer</code> such that <code>answer[i]</code> is the number of days you have to wait after the <code>i^th</code> day to get a warmer temperature. If there is no future day for which this is possible, keep <code>answer[i] == 0</code> instead.

**Example 1:**

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

**Example 2:**

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

**Example 3:**

Input: temperatures = [30,60,90]
Output: [1,1,0]

**Constraints:**

- <code>1 <=temperatures.length <= 10⁵</code>
- <code>30 <=temperatures[i] <= 100</code>

## Solution 1 - Monotone Stack
#### Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0] * n
        stack = []

        for idx, tem in enumerate(temperatures):
            while stack and tem > temperatures[stack[-1]]:
                i = stack.pop()
                res[i] = idx - i
            stack.append(idx)

        return res

#### C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> st;
        vector<int> res(n, 0);
        for (int i = 0; i < temperatures.size(); i++) {
            while (!st.empty() && temperatures[st.back()] < temperatures[i]) {
                res[st.back()] = i - st.back();
                st.pop_back();
            }
            st.push_back(i);
        }
        return res;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
[monotone stack](https://hackmd.io/@meyr543/rkjS-x6wY)