Максимальная длина диапазона, при которой A[i] является максимальным в заданном диапазоне для всех i из [1, N]

Дан массив arr[] , состоящий из N различных целых чисел. Для каждого i (0 ≤ i < n) найдите диапазон [l, r] такой, что A[i] = max(A[l], A[l+1], …, A[r]) и l ≤ i ≤ r и rl максимально.

Примеры:

Input: arr[] = {1, 3, 2}
Output: {0 0}, {0 2}, {2 2}
Explanation: For i=0, 1 is maximum in range [0, 0] only. For i=1, 3 is maximum in range [0, 2] and for i = 2, 2 is maximum in range [2, 2] only.

Input: arr[] = {1, 2}
Output: {0, 0}, {0, 1}

Наивный подход: самый простой подход к решению проблемы - для каждого i выполнить итерацию в диапазоне [i+1, N-1] с использованием переменной r и выполнить итерацию в диапазоне [i-1, 0] с использованием переменной l и завершить цикл. когда arr[l] > arr[i] и arr[r]>arr[i] соответственно. Ответ будет [l, r] .

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

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

• Инициализируйте два вектора, скажем, левый и правый , которые будут хранить левый индекс и правый индекс для каждого i соответственно.
• Инициализируйте стек пар, скажем, s .
• Вставьте INT_MAX и -1 как пару в стек.
• Выполните итерацию в диапазоне [0, N-1], используя переменную i , и выполните следующие шаги:
  • Пока s.top().first<arr[i] извлекает верхний элемент из стека.
  • Измените значение left[i] как s.top().second .
  • Поместите {arr[i], i} в стек.
• Теперь удалите все элементы из стека.
• Вставьте INT_MAX и N в стек парами.
• Выполните итерацию в диапазоне [N-1, 0], используя переменную i , и выполните следующие шаги:
  • Пока s.top().first<arr[i] извлекает верхний элемент из стека.
  • Измените значение right[i] как s.top().second .
  • Поместите {arr[i], i} в стек.
• Выполните итерацию в диапазоне [0, N-1], используя переменную i , и выведите left[i] +1 , right[i] -1 в качестве ответа для i -го элемента.

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

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