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

1. Идея

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

Иными словами, требуется вычислить:

max(a) - min(a)

Самый простой способ — пройти по всем элементам массива один раз, одновременно поддерживая:

• mn — минимальное значение среди уже просмотренных,
• mx — максимальное значение среди уже просмотренных.

После этого ответом будет mx - mn.

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

1. Чтобы найти разброс, не нужно сортировать массив.
2. Достаточно знать только два числа:
   • самый маленький элемент,
   • самый большой элемент.
3. Если массив состоит из одного элемента, то минимум и максимум совпадают, поэтому ответ равен 0.
4. Ограничение n <= 2 * 10^5 подсказывает, что решение за O(n) подходит отлично.

3. Алгоритм

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

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

При просмотре массива слева направо мы всегда храним:

• минимальный элемент среди всех уже встреченных,
• максимальный элемент среди всех уже встреченных.

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

• 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)