Given a list of integers that represents the daily temperatures, we want to calculate the number of days one has to wait to see a higher temp calculated for each day.
Example
nums = [9,6,10,4,11]
Ans = [2,1,2,1,0]
Example
nums = [73,72,71,70,90]
Ans = [4,3,2,1,0]
Example
nums = [73,72,71,70]
Ans = [0,0,0,0]
Solution
The right data structure for this is stack.
We need to push the daily temps in the stack as long as we don't see a higher temperature. But when we do, we keep removing them one by one from the stack and calculate the distance. For this purpose we need to store the index of the temp array not the actual values.
In the case where we won't see any temp increase, we don't need to do any thing since we have already initialized all the elements of the result array as 0.
public int[] DailyTemperatures(int[] temperatures) {
int n = temperatures.Length;
int[] result = new int[n];
Stack<int> stack = new Stack<int>();
for (int i = 0; i < n; i++) {
while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()]) {
int prevIndex = stack.Pop();
result[prevIndex] = i - prevIndex;
}
stack.Push(i);
}
return result;
}