Ряд солдатів (Розбір)

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

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

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

• занесемо у стек інформацію про поточного солдата, тобто пару (зріст солдата, номер солдата);

У будь-який момент часу стек зберігає солдатів, відсортованих за спаданням їх зросту. Коли приходить новий солдат, зі стеку видаляються всі солдати з меншим або рівним його зростом. Потім новий солдат займає місце на вершині стеку.

Приклад

Розглянемо обробку солдатів з прикладу.

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

Оголосимо стек $s$ для зберігання висот та індексів солдатів.

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

Читаємо вхідні дані.

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

Послідовно обробляємо $n$ солдатів.

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

Видаляємо зі стеку солдатів, чиї висоти не перевищують висоту $i$-го солдата.

  while (!s.empty() && s.top().first \u003c= 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] \u003c= h[i]:
    s.pop()

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

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

Поточний солдат у стеку є найближчим попереднім солдатом, зріст якого перевищує зріст $i$ - го солдата.

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

Заносимо інформацію про поточного солдата у стек.

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