Разбор задачи «Размах массива»

1. Идея

Нужно найти разность между самым большим и самым маленьким элементом массива.

То есть задача сводится к поиску:

• минимума массива mn
• максимума массива mx

После этого ответ равен mx - mn.

2. Наблюдения

1. Если в массиве только один элемент, то он одновременно и минимум, и максимум, поэтому ответ 0.

2. Если все элементы одинаковые, то минимум равен максимуму, и ответ тоже 0.

3. Чтобы найти размах массива, не нужно сортировать массив. Достаточно один раз пройти по всем элементам и поддерживать текущие:

   • минимальное значение
   • максимальное значение

4. Ограничение n <= 2 * 10^5 легко позволяет сделать один линейный проход.

3. Алгоритм

1. Считываем n.
2. Считываем элементы массива.
3. Берём первый элемент как начальные значения:
   • mn = a[0]
   • mx = a[0]
4. Проходим по остальным элементам:
   • если текущий элемент меньше mn, обновляем mn
   • если текущий элемент больше mx, обновляем mx
5. Выводим mx - mn.

4. Почему это работает

Во время прохода по массиву:

• mn всегда хранит наименьший из уже просмотренных элементов
• mx всегда хранит наибольший из уже просмотренных элементов

Это верно с самого начала, потому что после чтения первого элемента и mn, и mx равны ему.

Дальше для каждого нового элемента x:

• если x < mn, значит найден новый минимум
• если x > mx, значит найден новый максимум

После обработки всех элементов:

• mn — минимум всего массива
• mx — максимум всего массива

По условию требуется разброс температур, то есть разность между максимальной и минимальной температурой. Именно это значение и вычисляется как mx - mn.

5. Сложность

• Время: O(n), потому что массив просматривается один раз
• Память:
  • в приведённом решении на C++: O(1), так как элементы можно обрабатывать по мере чтения
  • в приведённом решении на Python: O(n), так как массив сначала сохраняется в список

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long x;
    cin >> x;
    long long mn = x, mx = x;

    for (int i = 1; i < n; i++) {
        cin >> x;
        if (x < mn) mn = x;
        if (x > mx) mx = x;
    }

    cout << (mx - mn) << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

mn = a[0]
mx = a[0]

for x in a[1:]:
    if x < mn:
        mn = x
    if x > mx:
        mx = x

print(mx - mn)