Проверьте, можно ли выбрать тройку зданий, чтобы третье здание было выше первого и меньше второго.

Дан массив arr[] , состоящий из N целых чисел, где каждый элемент массива представляет собой высоту здания, расположенного по координате X , задача состоит в том, чтобы проверить, можно ли выбрать 3 здания так, чтобы третье выбранное здание было выше первого выбранного здания и ниже второго выбранного здания.

Примеры:

Input: arr[] = {4, 7, 11, 5, 13, 2}
Output: Yes
Explanation:
One possible way is to select the building at indices [0, 1, 3] with heights 4, 7 and 5 respectively.

Input: arr[] = {11, 11, 12, 9}
Output: No

Подход: Данная проблема может быть решена с использованием структуры данных Stack. Выполните следующие шаги, чтобы решить проблему:

• Если N меньше 3 , то выведите « Нет ».
• Инициализируйте массив, скажем, preMin[], чтобы сохранить минимальный массив префикса массива arr[].
• Пройдите массив arr[] и обновите preMin[i] как preMin[i] = min(preMin[i-1], arr[i]).
• Теперь инициализируйте стек, скажем , стек, чтобы хранить элементы с конца в порядке возрастания.
• Обойдите массив arr[] в обратном порядке, используя переменную, скажем , i, и выполните следующие шаги:
  • Если arr[i] больше, чем preMin[i] , выполните следующие действия:
    • Итерировать, пока стек не пуст, а верхний элемент стека меньше, чем preMin[i], а затем извлекать верхний элемент стека на каждой итерации.
    • Если стек не пуст и верхний элемент стека меньше, чем arr[i], то выведите « Да » и вернитесь.
    • В противном случае, после вышеуказанного шага, поместите arr[i] в стек .
• После выполнения вышеуказанных шагов, если ни один из вышеперечисленных случаев не удовлетворяет, то выведите « Нет ».

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

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