739. Daily Temperatures

Задача

Дан массив температур. Для каждого дня верните, сколько дней ждать более тёплого дня (0, если такого нет).

Примеры

Пример 1

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Пример 2

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Пример 3

Input: temperatures = [30,60,90]
Output: [1,1,0]

Решение

Решение

/**
 * Time Complexity: O(n) - каждый элемент добавляется и удаляется из стека максимум один раз
 * Space Complexity: O(n) - стек может содержать до n элементов
 * 
 * Решение: используем монотонный убывающий стек для хранения индексов.
 * Когда встречаем температуру выше, чем на вершине стека - нашли ответ
 * для всех элементов в стеке, которые меньше текущего
 */
var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    const stack = []; // храним индексы
 
    for (let i = 0; i < n; i++) {
        // Пока стек не пуст И текущая температура выше, чем на вершине стека
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex; // количество дней ожидания
        }
 
        stack.push(i); // добавляем текущий индекс
    }
 
    return result;
};