Сложность: medium
Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.
Пример:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
👨💻 Алгоритм:
1⃣Создайте стек для хранения индексов дней с температурами, для которых еще не найден более теплый день.
2⃣Пройдите по массиву температур и для каждого дня: Пока текущая температура больше температуры дня на вершине стека, обновляйте массив ответов и удаляйте вершину стека. Добавьте текущий день в стек.
3⃣Возвращайте массив ответов.
😎 Решение:
public class Solution {
public int[] dailyTemperatures(int[] T) {
int n = T.length;
int[] answer = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
int j = stack.pop();
answer[j] = i - j;
}
stack.push(i);
}
return answer;
}
}Ставь 👍 и забирай 📚 Базу знаний