Daily Temperatures
Leetcode #739 | Medium | Монотонный стек | Стек
Идея
Идея монотонного стека. Кладем дни в стек, как бы садим на скамейку. При проходе по очередному дню смотрим на вершину стека, если день теплее, то он "забирает" день со стека в результат. И так далее собирает пока не станет слишком "холодным" для ждущего, либо пока стек не закончится. Монотонный - потому что в стеке температуры будут только возрастать, если на понижение - то день уходит в результат.
Big-O
- Время
O(N) - Память
O(N)
Код
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
Deque<Integer> stack = new ArrayDeque<>();
int[] res = new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++) {
while (stack.size() > 0 && temperatures[i] > temperatures[stack.peek()]) {
int pickedIndex = stack.pop();
res[pickedIndex] = i-pickedIndex;
}
stack.push(i);
}
return res;
}
}