Подготовка к собеседованию в Google — Хитрая задача на Стек

Разбираем довольно сложную алгоритмическую задачу по программированию с применением стека. Ее могут спросить на собеседовании в Google, Amazon и Facebook.

[old_relokant]

Вы прекрасно объясняете алгоритмы и структуры данных. Это очень большая редкость. Надеюсь что Вы вернётесь к ведению канала и будете продолжать просвещать начинающих it-специалистов.

[jury]

Лучшее объяснение алгоритмов, нет слов, просто потрясающще!!!

[iliarodin]

Александр, очень нравится как вы объясняет материал. Спокойно и понятно. Спасибо.

[tormizor]

Парень прирожденный препод! :) Очень доходчиво.

[Svetoz]

Интересная задача и очень понятное объяснение решения! Спасибо!

[Alkor]

С таким кайфом вообще смотрю, спасибо огромное

[Vitek_]

Спасибо за пример и хорошее объяснение! 👍

[azatakhunov]

Решение со Stack прошло проверку. Спасибо за видео! лайк и подписка

[denicfor]

Отличное объяснение! У меня сначала появилась идея просто отсортировать массив по убыванию с сохранением индексов и потом бежать по нему и выделять в подмассив длинны n ответы по индексу элемента в подмассиве, но ваш вариант определенно лучше во всех случаях)

[kbuycce]

Спасибо за видео, понятно объясняете

[toster]

Позитивная подача и интересный материал !

[opgroev]

Очень хорошее объяснение и залача, спасибо

[levorlov]

Интересная задача. Спасибо вам за такое хорошее и понятное объяснение!)

[bohdansolonenko]

Если не ошибаюсь, то стек тут не нужен, проблему можно решить за это же время без дополнительной памяти:

vector<int> arr = {13, 12, 15, 11, 9, 12, 16};
vector<int> res;
res.resize(arr.size(), 0);


for(int i = res.size() - 2; i >= 0; --i) {
int j = i + 1;
while(res[j] != 0 && arr[j] <= arr[i]) j += res[j];
if(arr[j] > arr[i]) res[i] = j - i;
}

[PointWand]

Прекрасное лаконичное изложение материала, спасибо. В стек не обязательно сохранять значения, достаточно просто индексы. По ним в исходном массиве находим значение.

[MagicMightNew]

Array.prototype.last = function() {return this[this.length - 1] ?? undefined}

let n = [13, 12, 15, 11, 9, 12, 16]
let stack = []
let answer = new Array(n.length).fill(0)

n.forEach((el, idx) => {
while (n[stack.last()] < el) {
let val = stack.pop()
answer[val] = idx - val
}
stack.push(idx)
})

console.log(answer)

У меня получилось такое решение (JS), до того как посмотрел разбор. Спасибо большое за задачу :)

[Selex]

Красава вапще, я не могу просто над тобой, лайк, подписка, и high recommended

[powerhead]

Хорошее решение. Нет необходимости хранить в стеке значения температур, достаточно класть туда только индексы:

public int[] warmDays(int[] days) {

result = new int[days.length];

Stack<Integer> stack = new Stack<>();

for(int day = days.length-1; day >= 0; day--) {
while (!stack.isEmpty() && days[stack.peek()] <= days[day]) {
stack.pop();
}
if(!stack.isEmpty()) {
result[day] = stack.peek() - day;
}
stack.push(day);
}
return result;
}

[HideDJeker]

С временной сложностью не совсем очевидно, но именно взаимодействий со стеком (вставок и удалений) в худшем случае <2N : (N, 1..(N-1)) в самом конце будет N-1 операций удаления и N-2 до этого вставок. Ну а дальше уже отбрасываем константу и получается N.

[kushok]

Можно идти по списку и в прямом порядке:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = [] # [(i1, t1), (i2, t2), ...]
result = [0] * len(temperatures)

for i, t in enumerate(temperatures):
while stack and stack[-1][1] < t: # stack[-1] means the last element
prev_i = stack.pop()[0]
result[prev_i] = i - prev_i

stack.append((i, t))

return result