Максимальное расстояние между пиками в данном связанном списке

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

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

Примеры:

Input: lis = 1 -> 2 -> 3 -> 1 -> 5 -> 4 -> 4 -> 10 -> 7
Output: 2
Explanation: The peaks in the linkedlist are 3, 5, 10
The distance between 3 and 5 is 1. 
The distance between 5 and 10 is 2.
The maximum distance is 2.

Input: lis = 1 -> 3 -> 1 -> 1 ->1 -> 1 -> 4 -> 2 -> 7
Output: 4
Explanation: The peaks in the linkedlist are 3, 4, 7
The distance between 3 and 4 is 4.
The distance between 4 and 7 is 1.
The maximum distance is 4.  

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

  • Переберите связанный список и найдите узлы, которые являются пиками.
  • Сохраняйте запись предыдущего индекса, который является пиковым, и текущего индекса, если это пик.

Ниже приведена реализация описанного выше подхода.

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

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