Поиск наивысших значений в массиве на некотором расстоянии друг от друга

Question

У меня есть массив ints, которые представляют высоты, и мне нужно выяснить, сколько из этих высот сможет увидеть горизонт на западе (массив организован с запада на восток). Требование видеть горизонт выше, чем последние n/5 высоты, где n - длина массива.

Это было бы легко с двумя циклами, но я должен сделать это в O (n). Поэтому я могу только перебирать массив сразу. Мне не нужно решение, просто нажмите в правильном направлении.

Answer 1

Что о работе в обратном направлении через массив? Начните с конца и создайте очередь каждой высоты, которую вы проходите. Если вы видите, что высота больше текущей, то ни одна из высот в очереди не может видеть горизонт (так что вы можете выбросить их). Если вы доберетесь до n/5, то последняя высота в очереди может видеть горизонт (и, очевидно, вам нужно будет обрабатывать более чем n/5 элементов в очереди).

Answer 2

Вы должны действительно прочитать эту
http://en.wikipedia.org/wiki/Selection_algorithm

Answer 3

Высота над уровнем моря будет иметь возможность видеть горизонт, если она максимальная, в скользящем окне размером = n/5.

«Максимальное скольжение (перемещение) окна» имеет сложность O (n). Его можно найти как в SO, так и в Интернете.

Подсказка: используйте простые структуры данных - очереди или стеки