---
# System prepended metadata

title: LC 739. Daily Temperatures
tags: [medium, leedcode, python, Monotone Stack, c++]

---

# 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<sup>th</sup></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<sup>5</sup></code>
- <code>30 <=temperatures[i] <= 100</code>

## Solution 1 - Monotone Stack
#### Python
```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++
```cpp=
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)
