Максимальное количество людей, которых может видеть человек, стоя в очереди в обоих направлениях

Дан массив height[] , который представляет рост N человек, стоящих в очереди. Человек i может видеть человека j , если height[j] < height[i] и между ними нет человека k , такого что height[j] ≥ height[i] . Найдите максимальное количество людей, которых может видеть человек.

Примечание: Человек может видеть любого другого человека, независимо от того, стоят ли они перед ним или сзади.

Примеры:

Input: heights[] = {6, 2, 5, 4, 5, 1, 6}.
Output: 6
Explanation:
Person 1 (height = 6) can see five other people at following positions (2, 3, 4, 5. 6) in addition to himself, i.e. total 6.
Person 2 (height: 2) can see only himself.
Person 3 (height = 5) is able to see people 2nd, 3rd, and 4th person.
Only Person 4 (height = 4) can see himself.
Person 5 (height = 5) can see people 4th, 5th, and 6th.
Person 6 (height =1) can only see himself.
Person 7 (height = 6) can see 2nd, 3rd, 4th, 5th, 6th, and 7th people.
A maximum of six people can be seen by Person 1, 7th

Input: heights[] = {1, 3, 6, 4 }
Output: 3

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

• Поддерживайте левый указатель (leftptr ), указывающий на idx-1 , и правый указатель (rightptr) , указывающий на idx+1 .
• Двигайте левый указатель влево, пока не найдете человека, чей рост больше или равен height[idx] .
• Двигайте правый указатель в нужном направлении, пока не найдете человека, чей рост больше или равен высоте [idx] .
• Разница между индексами правого и левого указателя дает нам количество людей, которых i -й человек может видеть и обновлять Ans как max(Ans, rightptr – leftptr-1) .

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

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

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

• Создайте массив r_heights размера N для хранения индекса следующего большего человека (справа).
• Чтобы найти положение следующего большего человека справа:
• поместите последний индекс массива в стек.
• Для каждого индекса в диапазоне от N-1 до 0 :
• продолжайте извлекать индексы из стека, пока не найдете индекс, высота которого больше или равна росту текущего человека, или пока стек не станет пустым.
• Если стек не пуст, обновите значение r_heights[i] так , чтобы оно соответствовало вершине стека, иначе r_heights[i]=N.
• Поместите текущий индекс в стек.
• Итерируйте от 0 до N , чтобы найти индекс следующего большего человека слева для каждого человека в строке.
• Для каждого человека в строке количество людей, которых он может видеть, равно r_heigths[i]-l_heights[i]-1 . Обновите Ans как max(Ans, r_heigths[i]-l_heigths[i]-1)

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

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