Минимальные прыжки, необходимые для достижения всех элементов массива с использованием самого большого элемента

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

Примеры:

Input: arr[] = {1, 3, 6, 5}
Output: [2, 1, 0, 1]
Explanation:
Below are the jumps required to reach each platform:

• For the 1st platform, the jump from the 3rd platform to the 2nd platform, then jump to the 1st platform is required. Hence, a total of 2 jumps are required.
• For the 2nd platform, the jump from the 3rd platform directly to the 2nd platform is required. Hence, a total of 1 jump are required.
• For the 3rd platform, we are already on the 3rd platform. Hence, a total of 0 jumps are required.
• For the 4th platform, the jump from the 3rd platform directly to the 4th platform is required. Hence, a total of 1 jump are required.

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

Подход: данная проблема может быть решена с помощью динамического программирования, основанного на наблюдении, что минимальный возможный переход от самого большого элемента к i ^-му элементу на единицу больше, чем минимум минимальных прыжков, необходимых для следующего большего элемента в левой или Правильно. Итак, идея состоит в том, чтобы предварительно вычислить результаты более крупных элементов и использовать их для поиска ответов на более мелкие элементы. Выполните следующие шаги, чтобы решить данную проблему:

• Для каждого элемента массива arr[i] хранит два индекса L и R , представляющие индекс следующего большего элемента слева и справа на карте соответственно.
• Отсортируйте массив arr[] по убыванию.
• Инициализируйте вектор, скажем, ans[] , который хранит минимальные переходы для всех элементов массива.
• Перейдите массив arr[] и выполните следующие шаги:
  • Если текущий элемент массива является самым большим элементом, то для текущего элемента требуется 0 переходов.
  • Найдите расстояние до следующего большего элемента слева и справа от текущего элемента, используя значение, хранящееся в картах. Сохраните расстояния в переменных L и R соответственно.
  • Обновите значение минимальных прыжков, скажем, M в соответствии со следующими критериями:
    • Если L не меньше 0, а R меньше N, то значение M равно min(ans[L], ans[R]) + 1.
    • Если L меньше 0, а R меньше N, то значение M равно ans[R] + 1.
    • Если L не менее 0 и R не менее N, то значение M равно ans[L] + 1.
  • Обновите значение минимальных переходов для текущего индекса как значение M .
• После выполнения вышеуказанных шагов выведите массив ans[] в качестве результирующих скачков индексов.

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

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