Разбор

Объявим стек пар, который будет хранить информацию о солдатах: их рост и индекс. Будем обрабатывать солдат по очереди, начиная с самого левого. При обработке $i$-го солдата:

• удалим из стека солдат, чей рост не превышает роста $i$-го солдата (то есть тех солдат, чей рост меньше или равен росту $i$-го солдата);

• солдат на вершине стека будет ближайшим предыдущим солдатом, рост которого превышает рост $i$ - го солдата. Если стек оказывается пустым, то $i$-ый солдат имеет четкую видимость;

• занесем в стек информацию о текущем солдате, то есть пару (рост солдата, номер солдата);

В любой момент времени стек хранит солдат, отсортированных по убыванию их роста. Когда приходит новый солдат, из стека удаляются все солдаты с меньшим или равным его ростом. Затем новый солдат занимает место на вершине стека.

Пример

Рассмотрим обработку солдат из примера.

Реализация алгоритма

Объявим стек $s$ для хранения высот и индексов солдат.

stack<pair<int, int> > s; // (height, index)

Читаем входные данные.

scanf("%d", &n);
h.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &h[i]);

Последовательно обрабатываем $n$ солдат.

for (i = 0; i < h.size(); i++)
{

Удаляем из стека солдат, чьи высоты не превышают высоту $i$-го солдата.

  while (!s.empty() && s.top().first <= h[i])
    s.pop();

Если стек пустой, то $i$-ый солдат имеет четкую видимость. То есть он видит всех солдат перед собой, и никто из них не блокирует ему вид.

  if (s.empty())
    printf("-1 ");
  else

Текущий солдат в стеке является ближайшим предыдущим солдатом, рост которого превышает рост $i$ - го солдата.

    printf("%d ", s.top().second);

Заносим информацию о текущем солдате в стек.

  s.push(make_pair(h[i], i));
}

Python реализация

Читаем входные данные.

n = int(input())
h = list(map(int, input().split()))

Объявим стек $s$ для хранения высот и индексов солдат.

s = []

Последовательно обрабатываем $n$ солдат.

for i in range(len(h)):

Удаляем из стека солдат, чьи высоты не превышают высоту $i$-го солдата.

  while s and s[-1][0] <= h[i]:
    s.pop()

Если стек пустой, то $i$-ый солдат имеет четкую видимость. То есть он видит всех солдат перед собой, и никто из них не блокирует ему вид.

  if not s:
    print("-1", end=" ")

Текущий солдат в стеке является ближайшим предыдущим солдатом, рост которого превышает рост $i$ - го солдата.

  else:
    print(s[-1][1], end=" ")

Заносим информацию о текущем солдате в стек.

  s.append((h[i], i))