739. Daily Temperatures
Đề Bài
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 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:
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
C++
0739-daily-temperatures.cpp
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
const int n = temperatures.size();
stack<int> st;
vector<int> ans(n, 0);
for (int i = 0; i < n; ++i) {
while (!st.empty() and temperatures[st.top()] < temperatures[i]) {
ans[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return ans;
}
};
Python
0739-daily-temperatures.py
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and temperatures[i] >= temperatures[stack[-1]]:
stack.pop()
if stack:
ans[i] = stack[-1] - i
stack.append(i)
return ans