Növbəti böyük element (Həll təhlili)

Tam ədədlərdən ibarət bir stek təyin edək ki, gələcək böyük elementlər haqqında məlumatı saxlamaq üçün istifadə ediləcək. Massiv $a$-nin ədədlərini ardıcıl olaraq — sağdan sola doğru işləyəcəyik. $i$ indeksli elementi işləyərkən:

• $a[i]$-dən böyük olmayan bütün ədədləri stekdən silək;

• əgər stek boş deyilsə, stekin üstündəki ədəd $a[i]$ üçün növbəti böyük element olacaq; əgər stek boşdursa, növbəti böyük element olaraq $-1$ təyin edək;

• sonra stekə $a[i]$ ədədini əlavə edək.

Hər an stek ədədləri azalan ardıcıllıqla saxlayır. Növbəti ədəd gəldikdə, stekdən ondan böyük olmayan bütün elementlər silinir, sonra bu ədəd stekin üstünə yerləşdirilir.

Nümunə

Nümunədəki ədədlərin işlənməsini nəzərdən keçirək.

Alqoritmin reallaşması

Giriş məlumatlarını oxuyuruq.

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

Ədədləri ardıcıl olaraq sağdan sola işləyirik.

for (i = n - 1; i >= 0; i--)
{

Stekin üstündən $m[i]$-dən kiçik və ya ona bərabər olan bütün ədədləri silirik.

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

$m[i]$-dən sonrakı böyük element stekin üstündə olacaq. Əgər stek boşdursa, nəticə massivinə $-1$ əlavə edirik.

  if (s.empty()) res.push_back(-1);
  else res.push_back(s.top());

$m[i]$ ədədini stekə daxil edirik.

  s.push(m[i]);
}

Nəticə massivini əks etdiririk və çap edirik.

reverse(res.begin(), res.end());
for (i = 0; i < n; i++)
  printf("%d ", res[i]);
printf("\n");

Python reallaşması

Giriş məlumatlarını oxuyuruq.

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

Siyahıları temp olaraq təyin edirik.

res = []
s = []

Ədədləri ardıcıl olaraq sağdan sola işləyirik.

for i in range(n - 1, -1, -1):

Stekin üstündən $m[i]$-dən kiçik və ya ona bərabər olan bütün ədədləri silirik.

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

$m[i]$-dən sonrakı böyük element stekin üstündə olacaq. Əgər stek boşdursa, nəticə siyahısına $-1$ əlavə edirik.

  if not s:
    res.append(-1)
  else:
    res.append(s[-1])

$m[i]$ ədədini stekə daxil edirik.

  s.append(m[i])

Nəticə siyahısını əks etdiririk və çap edirik.

res.reverse()
print(*res)