334. Increasing Triplet Subsequence

LeetCode problem

Задача

Дан целочисленный массив nums. Вернуть true, если существует тройка индексов (i, j, k) таких, что

• i < j < k и
• nums[i] < nums[j] < nums[k].

Если таких индексов нет, вернуть false.

Подсказки

Для решения этой задачи вам необходимо найти возможное максимальное и минимальное число до текущего числа, не используя дополнительное пространство памяти.

Подход

Мы можем обойти список, используя два указателя, чтобы хранить первое минимальное и последующие “два” минимальные значения, которые мы встретили до сих пор.

Затем, если мы находим число, которое больше обоих, это значит, что у нас есть тройка в последовательности.

Алгоритм

Алгоритм основан на идее поиска последовательности из трех возрастающих чисел.

Мы ищем два наименьших числа min1 и min2 из массива, и если мы находим третье число array[i], которое больше min2, то мы нашли требуемую последовательность.

В противном случае мы возвращаем false, так как набор чисел не удовлетворяет условиям задачи.

1. Объявляем две переменные - min1 и min2 - и инициализируем их максимально возможными значениями (INT_MAX).
2. Проходим через входной массив поэлементно.
3. Если текущий элемент array[i] меньше min1, обновляем min1 на array[i].
4. Если текущий элемент array[i] больше min1, но меньше min2, обновляем min2 на array[i].
5. Если текущий элемент array[i] больше min2, значит, у нас есть последовательность из трех чисел, удовлетворяющая условиям задачи. Возвращаем true.
6. Если после прохода по всем элементам мы не нашли такую последовательность, возвращаем false

Решение

def increasingTriplet(nums: list[int]) -> bool:
    # Инициализация минимальных значений
    min1 = float('inf')
    min2 = float('inf')

    for n in nums:
        if n <= min1:
            min1 = n
        elif n <= min2:
            min2 = n
        # Если число больше min2, значит у нас есть возрастающая тройка
        else:
            return True

    return False