План курса / Все задачи / Алгоритмы и структуры данных
Жаркий отпуск тихоходки
легко
# решено
Тихоходка может выдерживать температуру от -271 до 100 градусов и выживает в самых экстремальных условиях
Дан массив temperature, где temperature[i] - температура i-ой планеты. Тихоходка хочет хорошенько отдохнуть, но в свой отпуск она может посетить только k подряд идущих планет
Твоя задача найти максимальную среднюю температуру на k подряд идущих планетах, ведь тихоходка очень любит тепло :)
Пример 1:
Ввод: temperature = [1,2,0,-4], k = 2
Вывод: 1.5
Объяснение: [(1+2)/2, (2+0)/2, (0-4)/2] - возможные ответы, а наибольший это (1+2)/2=1.5
Пример 2:
Ввод: temperature = [10], k = 1
Вывод: 10.0
Ограничения:
len(temperature) ≥ 0
k ≥ 1
Значение массива temperature лежит в диапазоне [-271, 100] (включительно)
public class Solution {
public static double MaxAverageTemperature(List<int> temperature, int k) {
if (k > temperature.Count) {
return 0;
}
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += temperature[i];
}
int maxWindowSum = windowSum;
for (int i = k; i < temperature.Count; i++) {
windowSum = windowSum + temperature[i] - temperature[i - k];
if (windowSum > maxWindowSum) {
maxWindowSum = windowSum;
}
}
return (double) maxWindowSum / k;
}
}
#include <vector>
using namespace std;
double maxAverageTemperature(vector<int>& temperature, int k) {
if (k > temperature.size()) {
return 0;
}
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += temperature[i];
}
int maxWindowSum = windowSum;
for (int i = k; i < temperature.size(); i++) {
windowSum = windowSum + temperature[i] - temperature[i - k];
maxWindowSum = max(maxWindowSum, windowSum);
}
return static_cast<double>(maxWindowSum) / k;
}
package main
func max(x, y int) int {
if x > y {
return x
}
return y
}
func maxAverageTemperature(temperature []int, k int) float64 {
if k > len(temperature) {
return 0
}
windowSum := 0
for i := 0; i < k; i++ {
windowSum += temperature[i]
}
maxWindowSum := windowSum
for i := k; i < len(temperature); i++ {
windowSum = windowSum + temperature[i] - temperature[i-k]
maxWindowSum = max(maxWindowSum, windowSum)
}
return float64(maxWindowSum) / float64(k)
}
import java.util.*;
public class Solution {
public Double maxAverageTemperature(List<Integer> temperature, Integer k) {
if (k > temperature.size()) {
return 0.0;
}
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += temperature.get(i);
}
int maxWindowSum = windowSum;
for (int i = k; i < temperature.size(); i++) {
windowSum = windowSum + temperature.get(i) - temperature.get(i - k);
maxWindowSum = Math.max(maxWindowSum, windowSum);
}
return maxWindowSum / (double) k;
}
}
from typing import *
def max_average_temperature(temperature: List[int], k: int) -> float:
if k > len(temperature):
return 0
windowSum = 0
for i in range(k):
windowSum += temperature[i]
maxWindowSum = windowSum
for i in range(k, len(temperature)):
windowSum = windowSum + temperature[i] - temperature[i - k]
maxWindowSum = max(maxWindowSum, windowSum)
return maxWindowSum / k
/**
* @param {number[]} temperature
* @param {number} k
* @return {number}
*/
export function maxAverageTemperature(temperature, k) {
if (k > temperature.length) {
return 0;
}
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += temperature[i];
}
let maxWindowSum = windowSum;
for (let i = k; i < temperature.length; i++) {
windowSum = windowSum + temperature[i] - temperature[i - k];
maxWindowSum = Math.max(maxWindowSum, windowSum);
}
return maxWindowSum / k;
}
Оценка сложности
Время: O(n), где n - число элементов в temperature