# Daily Temperatures

`stack`, `monotonous stack`

Given a list of daily temperatures`T`, return a list such 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 of temperatures`T = [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]`.

## Analysis

### Brute-force

Brute-force的方法就略去不表，时间复杂度O(n^2)。

### Stack

Brute-force有很多是重复搜索，更有效率的是利用Stack，一个单调递增的stack。逆序的方式进行扫描。

`T = [73, 74, 75, 71, 69, 72, 76, 73]`

``````When i = 7, stack = [7 (73)]. ans[i] = 0.
When i = 6, stack = [6 (76)]. ans[i] = 0.
When i = 5, stack = [5 (72), 6 (76)]. ans[i] = 1.
When i = 4, stack = [4 (69), 5 (72), 6 (76)]. ans[i] = 1.
When i = 3, stack = [3 (71), 5 (72), 6 (76)]. ans[i] = 2.
When i = 2, stack = [2 (75), 6 (76)]. ans[i] = 4.
When i = 1, stack = [1 (74), 2 (75), 6 (76)]. ans[i] = 1.
When i = 0, stack = [0 (73), 1 (74), 2 (75), 6 (76)]. ans[i] = 1.``````

`ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;`

`T[i] >= T[stack.peek()]`时候要不断`pop()`，然后再放入当前下标i。这里要允许`"="`的条件，因为需要寻找第一个出现的位置，因此重复位置要`pop()`出来。

When I saw the question in this competition, I firstly think about Monotonous stack inspired by Largest Rectangle in Histogram. Because Monotonous stack can help us find first largest element in O(n) time complexity.

Time Complexity - O(n)

Space Complexity - O(n)

## Solution

Stack with reverse order iteration T.length - 1 to 0 - Time: O(n), Space: O(n) - (52 ms)

``````class Solution {
public int[] dailyTemperatures(int[] T) {
int[] ans = new int[T.length];
Deque<Integer> stack = new ArrayDeque<>();

for (int i = T.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
stack.pop();
}
ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
stack.push(i);
}
return ans;
}
}``````

Stack with 0 to T.length - 1 order iteration (17 ms, faster than 92.98%)

Using ArrayDeque() will significantly increase performance than Stack()

``````class Solution {
public int[] dailyTemperatures(int[] T) {
Deque <Integer> stack = new ArrayDeque<>();
int[] ret = new int[T.length];
for (int i = 0; i < T.length; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
int idx = stack.pop();
ret[idx] = i - idx;
}
stack.push(i);
}
return ret;
}
}``````

Brute-force O(n^2) - (348 ms)

``````class Solution {
public int[] dailyTemperatures(int[] T) {
int n = T.length;
int[] ans = new int[n];
int days = 0;
for (int i = 0; i < n; i++) {
days = 0;
for (int j = i; j < n; j++) {
if (T[j] > T[i]) {
ans[i] = days;
break;
} else {
days++;
}
}
}
return ans;
}
}``````

## Reference

https://leetcode.com/problems/daily-temperatures/solution/

https://leetcode.com/problems/daily-temperatures/discuss/109832/Java-Easy-AC-Solution-with-Stack

Last updated