Soldiers Row (Editorial)

Declare a stack of pairs that will store information about the soldiers: the height and index. We’ll process the soldiers one by one, starting from the leftmost one. When processing the $i$-th soldier:

• remove from the stack the soldiers whose height does not exceed the height of the $i$-th soldier (i.e., those soldiers whose height is less than or equal to the height of the $i$-th soldier);

• the soldier at the top of the stack will be the closest previous soldier whose height exceeds the height of the $i$-th soldier. If the stack is empty, then the $i$-th soldier has a clear visibility;

• push the information about the current soldier to the stack, that is, a pair (soldier's height, soldier's number);

At any given moment, the stack stores soldiers sorted in descending order of their height. When a new soldier arrives, all soldiers in the stack with a height less than or equal to his are removed. Then the new soldier takes the position at the top of the stack.

Example

Let's consider the processing of soldiers from the example.

Algorithm realization

Declare a stack $s$ to store the heights and indices of soldiers.

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

Read the input data.

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

Sequentially process $n$ soldiers.

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

Remove from the stack the soldiers whose heights do not exceed the height of the $i$-th soldier.

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

If the stack is empty, the $i$-th soldier has clear visibility. That is, he sees all the soldiers in front of him, and none of them block his view.

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

The current soldier at the top of the stack is the closest previous soldier whose height exceeds the height of the $i$-th soldier.

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

Push the information about the current soldier to the stack.

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

Python realization

Read the input data.

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

Declare a stack $s$ to store the heights and indices of the soldiers.

s = []

Sequentially process $n$ soldiers.

for i in range(len(h)):

Remove from the stack the soldiers whose heights do not exceed the height of the $i$-th soldier.

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

If the stack is empty, the $i$-th soldier has clear visibility. That is, he sees all the soldiers in front of him, and none of them block his view.

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

The current soldier at the top of the stack is the closest previous soldier whose height exceeds the height of the $i$-th soldier.

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

Push the information about the current soldier to the stack.

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