Əsgərlər sırası (Həll təhlili)

Əsgərlərin haqqında məlumat saxlayan cütlərdən ibarət bir yığın elan edək: boyları və indekslər. Əsgərləri soldan başlayaraq ardıcıl şəkildə emal edəcəyik. $i$-ci əsgərə baxarkən:

• Stəkdən $i$-ci əsgərin boyundan böyük olmayan əsgərləri (yəni boyu bərabər və ya kiçik olanları) çıxardaq;

• Yığının ən üstündəki əsgər, boyu $i$-ci əsgərin boyundan böyük olan ən yaxın əvvəlki əsgər olacaq. Əgər yığın boş çıxsa, $i$-ci əsgər açıq görünüşə malikdir;

• Cari əsgərin məlumatını, yəni (əsgərin boyu, əsgərin nömrəsi) cütlüyünü stəkə daxil edək;

Hər an yığın boylarının azalması qaydasında sıralanmış əsgərləri saxlayır. Yeni əsgər gələndə, ondan kiçik vəya ona bərabər olan bütün boylar yığından çıxarılır. Sonra yeni əsgər yığının ən üstünə yerləşdirilir.

Misal

Nümunədək əsgərlərin emalına baxaq.

Alqoritmin reallaşdırması

Əsgərlərin boy və indekslərini saxlamaq üçün yığın $s$ elan edək.

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

Giriş məlumatlarını oxuyaq.

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

$n$ əsgəri ardıcıl emal edirik.

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

$i$-ci əsgərin boyundan böyük olmayan əsgərləri yığından çıxarırıq.

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

Əgər yığın boşsa, $i$-ci əsgər açıq görünüşə malikdir. Yəni özündən əvvəlki əsgərləri görür və heç biri onun görünüşünü bloklamır.

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

Cari əsgər, boyu $i$-ci əsgərin boyundan böyük olan ən yaxın əvvəlki əsgərdir.

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

Cari əsgər haqqında məlumatı yığına daxil edirik.

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

Python reallaşdırması

Giriş məlumatlarını oxuyaq.

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

Əsgərlərin boy və indekslərini saxlamaq üçün yığın $s$ elan edək.

s = []

$n$ əsgəri ardıcıl emal edirik.

for i in range(len(h)):

$i$-ci əsgərin boyundan böyük olmayan əsgərləri yığından çıxarırıq.

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

Əgər yığın boşsa, $i$-ci əsgər açıq görünüşə malikdir. Yəni özündən əvvəlki əsgərləri görür və heç biri onun görünüşünü bloklamır.

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

Cari əsgər, boyu $i$-ci əsgərin boyundan böyük olan ən yaxın əvvəlki əsgərdir.

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

Cari əsgər haqqında məlumatı yığına daxil edirik.

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