Algorithm
Problem Name: 739. Daily Temperatures
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int>res(n);
stack < vector<int>>s; // stack of < temperature, index>
for(int i = 0; i < n; i++){
while(!s.empty() && temperatures[i] > s.top()[0]){
res[s.top()[1]] = i - s.top()[1];
s.pop();
}
s.push({temperatures[i], i});
}
return res;
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack stack = new Stack<>();
int[] ans = new int[T.length];
for (int i = T.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && T[stack.peek()] < = T[i]) {
stack.pop();
}
ans[i] = stack.isEmpty() ? 0 : (stack.peek() - i);
stack.push(i);
}
return ans;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const dailyTemperatures = function(T) {
const n = T.length;
const sk = [];
const res = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
let cur = T[i];
while (sk.length && T[sk[sk.length - 1]] < cur) {
let tail = sk.pop();
res[tail] = i - tail;
}
sk.push(i);
}
return res;
};
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
res = [0] * len(T)
heap = []
for j, t in enumerate(T):
while heap and heap[0][0] < t:
temp, i = heapq.heappop(heap)
res[i] = j - i
heapq.heappush(heap, (t, j))
return res
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0739_DailyTemperatures
{
public int[] DailyTemperatures(int[] T)
{
var stack = new Stack < int>();
var result = new int[T.Length];
for (int i = T.Length - 1; i >= 0; i--)
{
while (stack.Count > 0 && T[i] >= T[stack.Peek()])
stack.Pop();
result[i] = stack.Count == 0 ? 0 : (stack.Peek() - i);
stack.Push(i);
}
return result;
}
}
}
Input
Output