Найти 132 шаблона из заданного массива

Опубликовано: 19 Сентября, 2022

Дан массив arr[] размера N. Задача состоит в том, чтобы проверить, есть ли в массиве 3 элемента с индексами i , j и k , такие что i < j < k и arr[i] < arr[j] > arr[k] и обр[i] < обр[к] .

Примеры:

Input: N = 6, arr[] = {4, 7, 11, 5, 13, 2}
Output: True
Explanation: [4, 7, 5] fits the condition.

Input: N = 4, arr[] = {11, 11, 12, 9}
Output: False
Explanation: No 3 elements fit the given condition. 

Подход: Задачу можно решить, используя следующую идею:

Traverse the array from N-1 to 0 and check for every ith element if the greatest element on the right which is smaller than ith element is greater than the smallest element on the left of i then true else false. 

To find the greatest element smaller than ith element we can use Next Greater Element 

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Создайте вектор small[] .
  • Пройдите массив arr[] и поддерживать минимальное значение, которое является наименьшим значением arr[0, . . ., я].
    • Если нет элемента меньшего, чем Arr[i] , сохраните -1, иначе сохраните min .
  • Инициализируйте пустой стек (скажем, S ). Бежать петля от N-1 до 0 :
    • Если стек не пуст и верхний элемент в стеке <= small[i], то извлеките элемент;
    • Если стек не пуст и small[i] < Top element в стеке < arr[i] возвращает true.
    • В противном случае поместите arr[i] в стек.
  • Если условие не выполнено, вернуть false .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N).
Вспомогательное пространство: O(N).

РЕКОМЕНДУЕМЫЕ СТАТЬИ