Daily Temperatures

stack, monotonous stack

Given a list of daily temperaturesT, 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, put0instead.

For example, given the list of temperaturesT = [73, 74, 75, 71, 69, 72, 76, 73], your output should be[1, 1, 4, 2, 1, 1, 0, 0].

Note:The length oftemperatureswill 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