Задача. Шаблон 132
Задача: дан массив целых чисел - nums. Необходимо определить есть ли в исходном массиве шаблон 132.
Справка: шаблон 132 представляет собой подпоследовательность из 3х целых чисел nums[i], nums[j], nums[k], таких что i < j < k, а также nums[i] < nums[k] < nums[j].
Входные данные: nums - массив целых чисел, размер массива N чисел, где 1 <= N <= 10^5. Элементы массива - целые числа типа Int32.
- [1, 2, 3, 4]
Output: false - [3, 1, 4, 2]
Output: true
Пояснение: { 1, 4, 2 } - подпоследовательность удовлетворяет шаблону 132.
Разбор
Хочется еще раз отметить, что в задаче необходимо найти подпоследовательность, а не подмассив, это ключевая особенность этой задачи.
Так как нам необходимо просто определить, соот-т массив шаблону или нет, достаточно найти первое такое соот-е и вернуть true.
Идея алгоритма состоит в том, чтобы отслеживать средний элемент шаблона 132, то есть самый максимальный. И если далее мы встретим элемент массива меньший среднего, то мы нашли шаблон.
Для реализации этой идеи используем стек. Стек будет использоваться для сохранения предыдущих элементов, что позволит найти максимальный средний элемент среди возможных.
Алгоритм
- Создадим пустой стек и переменную middleValue = int.MinValue.
- Запустим цикл по элементам исходного массива, давайте начнем с конца.
- Если текущий элемент меньше middleValue, то мы нашли 1й элемент шаблона 132 и возвращаем true.
- Иначе пройдемся по всем элементам стек, пока текущий элемент больше чем элемент стека. Таким образом мы найдем максимальное значение для middleValue.
- Не забываем добавить текущий элемент в стек. - Если мы прошли по массиву и не нашли подпоследовательность, возвращаем false.