Второй по величине

1. Идея

Нужно найти не просто второй элемент по позиции, а второе по величине различное значение.

Например:

• в массиве 1 2 ответ 1;
• в массиве 5 5 4 4 5 4 ответ 4, потому что максимальное значение 5, а следующее отличное от него — 4.

Самый удобный способ — во время одного прохода по массиву поддерживать:

• mx1 — наибольшее значение;
• mx2 — второе по величине различное значение.

Тогда после обработки всех чисел ответом будет mx2.

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

Наблюдение 1

Если текущее число x больше mx1, то:

• старое mx1 становится кандидатом на второе место;
• значит, mx2 = mx1;
• а mx1 = x.

Наблюдение 2

Если x не больше mx1, оно все равно может улучшить второе место.

Это происходит, когда:

• x < mx1 — чтобы значение было отличным от максимума;
• x > mx2 — чтобы оно было лучше текущего второго места.

Тогда нужно сделать mx2 = x.

Наблюдение 3

Равные максимальному элементы нельзя записывать во второе место.

Именно поэтому проверка должна быть x < mx1, а не x <= mx1.

Например, для массива 5 5 4:

• первый 5 делает mx1 = 5;
• второй 5 не должен менять mx2;
• только 4 должен стать вторым различным максимумом.

Наблюдение 4

Так как гарантируется наличие хотя бы двух различных значений, ответ точно будет найден.

3. Алгоритм

1. Считать n.
2. Завести две переменные:
   • mx1 — текущий максимум;
   • mx2 — второй по величине различный максимум.
3. Изначально положить в них очень маленькие значения.
4. Для каждого числа x:
   • если x > mx1:
     • mx2 = mx1
     • mx1 = x
   • иначе если x < mx1 и x > mx2:
     • mx2 = x
5. Вывести mx2.

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

Докажем, что после обработки каждого элемента:

• mx1 — это наибольшее из уже просмотренных значений;
• mx2 — это второе по величине различное значение среди уже просмотренных.

Рассмотрим очередное число x.

Случай 1: x > mx1

Тогда найден новый максимум.

• Старый максимум теперь становится вторым по величине различным значением.
• Новый максимум — это x.

Поэтому:

• mx2 = старое mx1
• mx1 = x

Свойство сохраняется.

Случай 2: x < mx1 и x > mx2

Тогда x меньше максимума, значит может быть вторым различным значением. При этом x больше текущего mx2, значит оно лучше прежнего второго места.

Поэтому mx2 = x, и свойство снова сохраняется.

Случай 3: все остальные случаи

Это значит, что:

• либо x == mx1, и тогда оно не образует новое различное второе место;
• либо x <= mx2, и тогда оно не улучшает уже найденный второй максимум.

Значит, менять ничего не нужно.

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

• mx1 — максимальное значение массива;
• mx2 — второе по величине различное значение массива.

Именно его и нужно вывести.

5. Сложность

Мы делаем один проход по массиву.

• Время: O(n)
• Память: O(1)

В Python в эталонном решении массив считывается в список, поэтому фактически используется O(n) памяти на хранение входных данных, но сама идея алгоритма требует только две переменные.

6. Код на C++17

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

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

    long long mx1 = numeric_limits<long long>::min();
    long long mx2 = numeric_limits<long long>::min();

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;

        if (x > mx1) {
            mx2 = mx1;
            mx1 = x;
        } else if (x < mx1 && x > mx2) {
            mx2 = x;
        }
    }

    cout << mx2 << "\n";
    return 0;
}

7. Код на Python 3

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

neg_inf = -10**30
mx1 = neg_inf
mx2 = neg_inf

for x in a:
    if x > mx1:
        mx2 = mx1
        mx1 = x
    elif x < mx1 and x > mx2:
        mx2 = x

print(mx2)