Java
import java.util.Arrays;
import java.util.Stack;
/**
Given a list of daily temperatures, produce a list that, for each day in the input,
tells you how many days you would have to wait until a warmer temperature.
If there is no future day for which this is possible, put 0 instead.
For example,
given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73],
your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
*/
public class Daily_Temperatures {
// https://leetcode.com/articles/daily-temperatures/
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
if (temperatures == null || temperatures.length == 0) {
return result;
}
int[] next = new int[100 + 1]; // range [30,100]
Arrays.fill(next, Integer.MAX_VALUE);
for (int i = temperatures.length - 1; i >= 0; i--) {
int warmerIndex = Integer.MAX_VALUE;
for (int t = temperatures[i] + 1; t <= 100; t++) {
if (next[t] < warmerIndex) {
warmerIndex = next[t];
}
}
next[temperatures[i]] = i;
// if last day, then always 0
if (warmerIndex != Integer.MAX_VALUE) {
result[i] = warmerIndex - i;
}
}
return result;
}
}
class Solution_Stack {
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
if (temperatures == null || temperatures.length == 0) {
return result;
}
Stack<Integer> sk = new Stack<>();
for (int i = temperatures.length - 1; i >= 0; i--) {
while (!sk.isEmpty() && temperatures[i] >= temperatures[sk.peek()]) { // @note: >=
sk.pop();
}
result[i] = sk.isEmpty()? 0: sk.peek() - i;
sk.push(i);
}
return result;
}
}
}
Java
class Solution {
public int[] dailyTemperatures(int[] T) {
int length = T.length;
int[] waitingDays = new int[length];
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> indicesStack = new Stack<Integer>();
for (int i = 0; i < length; i++) {
int temperature = T[i];
while (!stack.isEmpty() && stack.peek() < temperature) {
int prevTemperature = stack.pop();
int index = indicesStack.pop();
waitingDays[index] = i - index;
}
stack.push(temperature);
indicesStack.push(i);
}
return waitingDays;
}
}