План курса / Все задачи / Алгоритмы и структуры данных
Прогноз потеплений
средне
# решено
Дан массив temperature, где temperature[i] — температура в i-й день. Нужно вернуть массив result, где result[i] — количество дней, через которое температура станет выше, чем в i-й день. Если потепления не будет, result[i] = 0.
Дни с одинаковой температурой не считаются потеплением.
Пример 1:
Ввод: temperature = [5,6,9,7,5,-1,8,11,2]
Вывод: [1,1,5,3,2,1,1,0,0]
Пример 2:
Ввод: temperature = [5,4,3]
Вывод: [0,0,0]
Пример 3:
Ввод: temperature = [2,3,4,5]
Вывод: [1,1,1,0]
Ограничения:
len(temperature) >= 1
public class Solution
{
public static List<int> PredictWarming(List<int> temperatures)
{
List<int> result = new List<int>();
// Инициализируем результат нулями
for (int i = 0; i < temperatures.Count; i++)
{
result.Add(0);
}
// В стеке всегда храним номер дня
Stack<int> stack = new Stack<int>();
for (int i = 0; i < temperatures.Count; i++)
{
int temperature = temperatures[i];
// Пока текущая температура больше, чем температура в стеке,
// извлекаем элементы из стека и вычисляем для них ответ
while (stack.Count > 0 && temperatures[stack.Peek()] < temperature)
{
int idx = stack.Pop();
result[idx] = i - idx;
}
// Добавляем текущий индекс в стек
stack.Push(i);
}
return result;
}
}
public class Solution
{
public static List<int> PredictWarming(List<int> temperatures)
{
List<int> result = new List<int>();
// Инициализируем результат нулями
for (int i = 0; i < temperatures.Count; i++)
{
result.Add(0);
}
// В стеке всегда храним номер дня
Stack<int> stack = new Stack<int>();
for (int i = 0; i < temperatures.Count; i++)
{
int temperature = temperatures[i];
// Пока текущая температура больше, чем температура в стеке,
// извлекаем элементы из стека и вычисляем для них ответ
while (stack.Count > 0 && temperatures[stack.Peek()] < temperature)
{
int idx = stack.Pop();
result[idx] = i - idx;
}
// Добавляем текущий индекс в стек
stack.Push(i);
}
return result;
}
}
#include <vector>
using namespace std;
vector<int> predictWarming(const vector<int>& temperatures) {
vector<int> result(temperatures.size(), 0);
// в стеке всегда храним номер дня
vector<int> stack;
for (int i = 0; i < temperatures.size(); ++i) {
int temperature = temperatures[i];
// пока текущая температура больше, чем температура в стеке,
// вынимаем и удаляем из стека элементы и вычисляем для них ответ
while (!stack.empty() && temperatures[stack.back()] < temperature) {
int idx = stack.back();
stack.pop_back();
result[idx] = i - idx;
}
stack.push_back(i);
}
return result;
}
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Solution {
public List<Integer> predictWarming(List<Integer> temperatures) {
List<Integer> result = new ArrayList<>();
// инициализируем результат нулями
for (int i = 0; i < temperatures.size(); i++) {
result.add(0);
}
// в стеке всегда храним номер дня
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < temperatures.size(); i++) {
int temperature = temperatures.get(i);
// пока текущая температура больше, чем температура в стеке,
// вынимаем и удаляем из стека элементы и вычисляем для них ответ
while (!stack.isEmpty() && temperatures.get(stack.peek()) < temperature) {
int idx = stack.pop();
result.set(idx, i - idx);
}
stack.push(i);
}
return result;
}
}
from typing import *
def predict_warming(temperatures: List[int]) -> List[int]:
result = [0] * len(temperatures)
# в стеке всегда храним номер дня
stack = []
for i, temperature in enumerate(temperatures):
# пока текущая температура больше, чем температура в стеке,
# вынимаем удаляем из стека элементы и
# вычисляем для них ответ
while len(stack) > 0 and temperatures[stack[-1]] < temperature:
idx = stack.pop()
result[idx] = i - idx
stack.append(i)
return result
export function predictWarming(temperatures) {
let result = new Array(temperatures.length).fill(0);
// в стеке всегда храним номер дня
let stack = [];
for (let i = 0; i < temperatures.length; i++) {
let temperature = temperatures[i];
// пока текущая температура больше, чем температура в стеке,
// вынимаем удаляем из стека элементы и
// вычисляем для них ответ
while (stack.length > 0 && temperatures[stack[stack.length - 1]] < temperature) {
let idx = stack.pop();
result[idx] = i - idx;
}
stack.push(i);
}
return result;
}