roma-dxunvrs
25 lines
1.4 KiB
Markdown
25 lines
1.4 KiB
Markdown
Leetcode #739 | #Medium | [[Монотонный стек]] | [[Стек]]
|
|
## Идея
|
|
Идея монотонного стека. Кладем дни в стек, как бы садим на скамейку. При проходе по очередному дню смотрим на вершину стека, если день теплее, то он "забирает" день со стека в результат. И так далее собирает пока не станет слишком "холодным" для ждущего, либо пока стек не закончится. Монотонный - потому что в стеке температуры будут только возрастать, если на понижение - то день уходит в результат.
|
|
## Big-O
|
|
- Время ```O(N)```
|
|
- Память ```O(N)```
|
|
## Код
|
|
```Java
|
|
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;
|
|
}
|
|
}
|
|
``` |