Daily Temperatures — Monotonic Stack Waiting Days
Sanjeev SharmaAdvertisement
Problem
For each day, return the number of days until a warmer temperature. If none, return 0.
Approach — Decreasing Monotonic Stack
Stack stores indices of pending days. Pop when current temperature is warmer; answer = current_index - popped_index.
Time: O(n) | Space: O(n)
Solutions
Python
class Solution:
def dailyTemperatures(self, temps: list[int]) -> list[int]:
n=len(temps); res=[0]*n; stack=[]
for i,t in enumerate(temps):
while stack and temps[stack[-1]]<t:
j=stack.pop(); res[j]=i-j
stack.append(i)
return res
C++
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& t){
int n=t.size(); vector<int> res(n,0); stack<int> st;
for(int i=0;i<n;i++){
while(!st.empty()&&t[st.top()]<t[i]){res[st.top()]=i-st.top();st.pop();}
st.push(i);
}
return res;
}
};
Java
class Solution {
public int[] dailyTemperatures(int[] t){
int n=t.length; int[] res=new int[n]; Deque<Integer> st=new ArrayDeque<>();
for(int i=0;i<n;i++){
while(!st.isEmpty()&&t[st.peek()]<t[i]){int j=st.pop();res[j]=i-j;}
st.push(i);
}
return res;
}
}
Complexity
- Time: O(n) | Space: O(n)
Advertisement
