მონოტონური სტეკი

ყოველი დღისთვის: რამდენ დღეში დათბება? ყოველი სვეტისთვის: რამდენად შეიძლება მართკუთხედის გაჭიმვა? „შემდეგი მეტის“ ეს კითხვები O(n²) შრომას ჰგავს, მაგრამ ერთი სტეკი ყველას ერთ გავლაში პასუხობს.

საშუალო⏱ 10 წთ

←ეყრდნობა

3სტეკი (LIFO) და გამოსახულების გამოთვლამონოტონური სტეკი ჩვეულებრივი სტეკია, რომელიც ამოაგდებს ყველაფერს, რაც პასუხი ვეღარ იქნება.0სირთულე და ზრდის ტემპითითო ელემენტი ერთხელ შედის და ერთხელ გამოდის, ამიტომ შიდა ციკლის მიუხედავად ჯამში O(n)-ია.

გზას უხსნის→

3რიგი (FIFO) და დეკიმონოტონური დეკი მოცურავი ფანჯრის მაქსიმუმს იძლევა: იგივე იდეა, ოღონდ ორივე ბოლოდან.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01შემდეგი მეტი ელემენტი

მოცემული მასივის ყოველი ელემენტისთვის ვიპოვოთ მარჯვნივ პირველი უფრო დიდი ელემენტი, ან -1, თუ ასეთი არ არის. 4 7 3 5 2 6 8 1-ისთვის პასუხებია 7 8 5 6 6 8 -1 -1.

აშკარა ამოხსნა ყოველი პოზიციიდან მარჯვნივ მიდის, სანამ უფრო დიდს არ იპოვის. კლებად მასივზე ყოველი ასეთი გავლა ბოლომდე მიდის, ანუ O(n²).

დააკვირდი, რას კარგავს ნელი გავლა. როცა 5-ს ვუყურებთ, ადრინდელი 3 ჯერ კიდევ პასუხს ელოდება, და 5 სწორედ ეს პასუხია. ყოველი ელემენტი პასუხია მის წინ მყოფი ყველა უფრო პატარა მომლოდინისთვის. ამიტომ მომლოდინეები სადმე შევინახოთ და ყოველმა ახალმა მნიშვნელობამ რამდენიც შეუძლია, იმდენს გასცეს პასუხი.

02სტეკი, რომელიც კლებადი რჩება

მომლოდინე ელემენტების ინდექსები სტეკში შევინახოთ. ვკითხულობთ მარცხნიდან მარჯვნივ; ყოველი a[i]-სთვის:

სანამ სტეკი ცარიელი არ არის და a[top] < a[i]: top-ის პასუხია a[i]; ვიღებთ მას სტეკიდან;
ვდებთ i-ს.

რატომ კმარა მხოლოდ სათავიდან აღება? იმიტომ, რომ სტეკში მნიშვნელობები ქვემოდან ზემოთ ყოველთვის კლებადია. თუ სათავის ქვემოთ რამე a[i]-ზე ნაკლები იქნებოდა, სათავე კიდევ უფრო ნაკლები იქნებოდა და უკვე ამოღებული. ამიტომ როგორც კი ≥ a[i] ელემენტს შევხვდებით, მის ქვემოთ ყველაფერი კიდევ უფრო დიდია და შეგვიძლია გავჩერდეთ.

რაც ბოლოს სტეკში რჩება, უფრო დიდს არ შეხვედრია: მისი პასუხია -1. ეს არის მონოტონური სტეკის შაბლონი.

i = 5-ზე ახალი მნიშვნელობა 6 პასუხობს 2-სა და 5-ს და 7-თან ჩერდება.

03რატომ არის O(n) და მისი ნათესავები

შიდა while ციკლი საშიშად გამოიყურება, მაგრამ იტერაციების ნაცვლად ელემენტებზე დავთვალოთ: ყოველი ინდექსი სტეკში ზუსტად ერთხელ თავსდება და მაქსიმუმ ერთხელ გამოდის. მთელი გაშვების ყველა pop ერთად მაქსიმუმ n-ია, ამიტომ მთლიანი შრომა O(n)-ია. დათვლის ამ ხერხს ამორტიზებული ანალიზი ჰქვია.

შედარებების შებრუნებით მთელ ოჯახს მივიღებთ:

შემდეგი ნაკლები ელემენტი: ვიღებთ, სანამ a[top] > a[i] (სტეკი ზრდადი რჩება);
წინა მეტი ან ნაკლები: პასუხია ის, რაც სათავეშია i-ს ჩადებამდე;
მნიშვნელობების ნაცვლად შეინახე მანძილი i − top, „თბილ დღემდე დარჩენილი დღეებისთვის“.

ჰისტოგრამაში უდიდესი მართკუთხედი ყოველი სვეტისთვის წინა და შემდეგ ნაკლებ ელემენტებს იყენებს.

ფასი ერთი შეხედვით

ყველა „შემდეგი მეტი“O(n)

push + pop≤ 2n

დამატებითი მეხსიერებაO(n)

დაიმახსოვრე

პასუხის მომლოდინე ელემენტები სტეკში შეინახე; ახალი ელემენტი სათავეში მყოფ ყველა უფრო პატარას პასუხობს.
სტეკი მონოტონური რჩება („შემდეგი მეტისთვის“ კლებადი), ამიტომ ამოღება პირველივე არანაკლებ ელემენტთან წყდება.
ყოველი ინდექსი ერთხელ თავსდება და მაქსიმუმ ერთხელ გამოდის, ამიტომ ჩადგმული ციკლი მთლიანობაში მაინც O(n)-ია.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: დააკვირდი მარჯვნივ სტეკს: მისი მნიშვნელობები ზემოთ ყოველთვის მცირდება. ყოველი ახალი სვეტი სათავეში მყოფ პატარებს აძევებს და მათ პასუხებს ავსებს.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

მასივი a

i	0	1	2	3	4	5	6	7
a[i]	4	7	3	5	2	6	8	1
შემდეგი მეტი	?	?	?	?	?	?	?	?

სტეკი (ინდექსები, მნიშვნელობები კლებადია)

(ცარიელია)

მიმდინარესტეკშიაპასუხი ნაპოვნია

8 მნიშვნელობიდან თითოეულისთვის ვიპოვოთ მარჯვნივ პირველი უფრო დიდი. უხეში ძალით ყველა წყვილს შევამოწმებდით, O(n²). „მომლოდინე“ ინდექსების სტეკით ამას ერთ გავლაში ვაკეთებთ.

ფსევდოკოდი

 1 stack<int> st;  // indices still waiting for an answer 2 for i in 0..n-1: 3   while !st.empty() && a[st.top()] < a[i]: 4     ans[st.top()] = a[i]; st.pop(); 5   st.push(i); 6 while !st.empty(): ans[st.top()] = -1; st.pop(); 7 // every index pushed once, popped once → O(n)

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

მასივი 2 1 5. როცა 5 მოდის, სტეკში 2-ისა და 1-ის ინდექსებია (სათავეში 1). რა ხდება?

№2

n ელემენტის მკაცრად კლებად მასივზე რამდენი pop ხდება გავლის დროს?

№3

ამის ნაცვლად შემდეგი ნაკლები ელემენტი გინდა. რა იცვლება?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeNext Greater Element I დამწყები↗LeetCodeDaily Temperatures საშუალო↗CSESNearest Smaller Values საშუალო↗LeetCodeLargest Rectangle in Histogram მოწინავე↗