Stack و Monotonic StackLIFO · push / pop / peek · matching · monotonic stack
في الفصل اللي فات (Binary Search) كنت بتشتغل على array مترتبة وبترمي نص الاحتمالات كل خطوة. دلوقتي هنبدأ أول data structure ليها قواعد: آخر حاجة دخلت هي أول حاجة تطلع. فكرة بسيطة، بس هي اللي بتحل الأقواس والـ undo وحساب الـ expressions، و«أول رقم أكبر مني على اليمين» في O(n) بدل O(n²).
هتطلع من الفصل ده وإنت عارف
- يعني إيه LIFO، وتعرف من كلام المسألة إن الحل stack، وأنهي نوع فيهم.
- تستخدم الـ array في JS كـ stack صح، وتعرف ليه الـ peek هو
stack[stack.length - 1]مشstack[stack.length]. - تحل Valid Parentheses و Min Stack و Evaluate RPN، وتعرف ليه القسمة فيها
Math.truncمشMath.floor. - تفهم الـ monotonic stack من جوه: ليه indices، وليه
whileمشif، وليه هو O(n) مع إن فيه loop جوه loop. - تشوف إن الـ recursion نفسها شغالة على stack اسمه call stack.
ليه Stack؟
خد المسألة دي: string فيه أقواس من تلات أنواع، () و [] و {}، وعايز تعرف هل متقفلة صح. أول فكرة: counter. تفتح قوس تزوّد، تقفل تنقّص، وفي الآخر لازم يبقى صفر.
ده شغال مع نوع واحد بس. جرّبه على "([)]": الـ counter بيخلص بصفر فبيقول true، مع إن الـ [ اتفتحت جوه الـ ( فلازم تتقفل قبلها. وحتى counter لكل نوع لوحده هيقول true برضه. المشكلة إن الـ counting بيضيّع الترتيب.
الـ key insight: لما ييجي قوس بيقفل، اللي يهمك بس هو آخر قوس اتفتح. آخر واحد دخل هو أول واحد يطلع، والـ data structure اللي بتعمل كده اسمها stack.
الـ stack ليه تلات operations بس: push (حط فوق)، pop (شيل اللي فوق ورجّعه)، و peek (بص على اللي فوق من غير ما تشيله). مفيش access للنص، والقيد ده هو بالظبط اللي بيخلّي كل operation O(1).
أشهر stack قدامك كل يوم هو زرار Back في الـ browser:
Back مرتين طلّع leetcode وبعدين youtube، يعني بعكس ترتيب الدخول بالظبط. ده الـ stack كله.
طب إزاي تعرف من كلام المسألة إن الحل stack أصلًا؟ ده الجزء الجاي.
إزاي تعرفه من المسألة
الـ stack بيظهر لما يبقى فيه حاجات مستنية، والأحدث فيهم هو اللي يتعامل الأول. الكلمات دي بتقولك إنه غالبًا stack:
"أول واحد جه أول واحد يتخدم" ده queue، والـ BFS برضه queue. أكبر عنصر في window متحركة ده deque، و top k ده heap.
| النوع | الفكرة | الـ stack فيه إيه | أشهر مسائل |
|---|---|---|---|
| Matching brackets / nesting | آخر حاجة اتفتحت تتقفل الأول | الـ openers اللي لسه مفتوحة | Valid Parentheses، Decode String |
| Simulation undo / backspace | آخر عملية أول واحدة تتلغي | اللي لسه ما اتلغاش | Backspace String Compare، Simplify Path |
| Expression evaluate | الـ operator بياخد آخر رقمين | أرقام مستنية operator | Evaluate RPN، Basic Calculator |
| Design stack + extra | stack بميزة زيادة في O(1) | العنصر ومعاه معلومة لكل مستوى | Min Stack |
| Monotonic next greater / smaller | أول أكبر أو أول أصغر | indices مستنية إجابتها، مترتبة | Daily Temperatures، Next Greater Element، Largest Rectangle |
flowchart TD
A["Stack?"] --> B{"Things open and must close in reverse order?"}
B -- yes --> M["Matching: push openers, pop on closers"]
B -- no --> C{"Undo the most recent action?"}
C -- yes --> S["Simulation: push actions, pop to undo"]
C -- no --> D{"An operator uses the last two values?"}
D -- yes --> E["Expression: a stack of numbers"]
D -- no --> F{"Next or previous greater / smaller?"}
F -- yes --> G["Monotonic stack of indices"]
F -- no --> H["Probably not a stack: queue, heap or hash map"]
اسأل نفسك الأسئلة دي بالترتيب ده.
قبل أي مسألة: إزاي تعمل stack في JS أصلًا، وكل operation بتكلّف كام؟
الـ Stack في JavaScript
JS مفيهاش class اسمها Stack، ومش محتاجها: الـ array العادية بتعمل الشغل، بشرط تشتغل من آخرها بس. آخر خانة هي الـ top.
constبتمنع إنstackيشاور على array تانية، مش بتمنع التعديل. فـ push و pop شغالين عادي.pushبتحط في آخر الـ array، يعني فوق. الـ 2 دخلت آخر واحدة، فهي اللي هتطلع الأول.- peek. ليه
- 1؟ الطول 3 والـ indices هي 0 و 1 و 2، فآخر index هوlength - 1. ولو كتبتstack[stack.length]هترجعundefinedمن غير أي error، وstack.at(-1)بديل صح. popبتشيل آخر عنصر وبترجّعه. O(1) لأن مفيش ولا عنصر تاني اتحرك.- isEmpty. هتكتب الشرط ده قبل أي pop أو peek تقريبًا.
- ترتيب الخروج (2 ثم 8 ثم 5) عكس ترتيب الدخول (5 ثم 8 ثم 2).
- خلي بالك: pop على stack فاضي في JS مش بيضرب error، بيرجّع
undefinedبهدوء (Java و Python بيرموا exception). فالـ bug بيبان بعدين في مكان تاني، وعشان كده اتعوّد تشيك علىlengthالأول.
| الـ operation | في JS | الوقت | ملاحظة |
|---|---|---|---|
| push | stack.push(x) | O(1) amortized | شرحها تحت |
| pop | stack.pop() | O(1) | بترجّع undefined لو فاضي |
| peek | stack[stack.length - 1] | O(1) | أو stack.at(-1) |
| isEmpty / size | stack.length | O(1) | |
| search | stack.includes(x) | O(n) | لو محتاجها كتير، الـ stack مش الأداة الصح |
يعني إيه O(1) amortized؟ الـ array محجوزلها مساحة أكبر من عدد عناصرها. لما تتملي، الـ engine بيحجز مساحة أكبر بنسبة ثابتة وبينقل كل العناصر في O(n). بس ده بيحصل نادرًا، فلو وزّعت التكلفة على كل الـ pushes، كل push في المتوسط O(1).
unshift و shift بيدّوا نفس ترتيب الـ stack، بس كل واحدة فيهم O(n)، لأن كل العناصر بتتزحلق خانة. على 10⁵ operation ده O(n²) و TLE. التفاصيل في Queue و Deque.
ولو الـ interviewer قالك "implement a stack"، لفّ الـ array في class صغيرة، وامنع الـ pop على stack فاضي:
الأداة جاهزة. يلا نرجع لمسألة الأقواس اللي الـ counter فشل فيها.
مثال محلول 1: Valid Parentheses
عندك string كله أقواس من الأنواع () و [] و {}. هل كل قوس اتفتح اتقفل بنفس نوعه، وبالترتيب الصح، يعني اللي اتفتح جوه يتقفل الأول؟
نفكّر فيها مع بعض
- افهم المطلوب: كل closer ليه opener من نوعه، والـ opener ده لازم يكون آخر واحد لسه مفتوح، ومفيش حاجة تفضل مفتوحة في الآخر.
- Brute force: شيل أي
()أو[]أو{}جنب بعض وكرّر. شغال، بس ممكن تحتاج n/2 لفة كل واحدة O(n)، يعني O(n²). - الـ key insight: الـ closer لازم يقابل آخر opener لسه مفتوح، و"آخر واحد" ده هو الـ top.
- الخطة: opener يعمل push. closer: الـ stack لازم ما يبقاش فاضي، والـ pop يطلّع نفس النوع. وفي الآخر الـ stack لازم يبقى فاضي.
- Edge cases: string فاضي (true)،
")"،"(("، وطول فردي (أكيد false).
- الـ map من الـ closer للـ opener، مش العكس. لحظة ما تقابل closer، هو اللي في إيدك، وهو اللي بتسأل بيه: "مين المفروض يكون فوق؟".
- الـ stack فيه الـ openers اللي لسه مفتوحة، بترتيب فتحها.
for...ofعلى الحروف على طول، فمفيش index ولا قلق<و<=.- opener: لسه مش هنعرف هو صح ولا لأ، فيستنى الـ closer بتاعه في الـ stack.
- closer والـ stack فاضي، يعني بنقفل حاجة ما اتفتحتش. في JS السطر ده ممكن يتشال لأن
pop()هترجّعundefinedوالشرط اللي بعده هيفشل، بس اكتبه صريح: أوضح، وفي C++ الـtop()على stack فاضي undefined behavior. - pop ومقارنة في سطر واحد. لو اللي طلع مش الـ opener المطلوب، يبقى النوع أو الترتيب غلط، فبنعمل early return.
- ليه مش
return true؟"(("عمرها ما دخلت الـ else، فهتطلع true غلط. أي حاجة فاضلة في الـ stack هي opener ما اتقفلش.
الخانات الخضرا في الـ string هي الأزواج اللي اتقفلت:
ودي الحالة اللي الـ counter غلط فيها. الـ stack بيمسكها عند أول closer:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| "" | true | الـ loop مش بتلف، والـ stack فاضي |
| "(" | false | فاضل opener، والسطر 12 بيمسكها |
| ")" | false | closer والـ stack فاضي، السطر 8 |
| "((" | false | return true في الآخر هتطلّعها غلط |
| "([)]" | false | الـ counter بيقول true هنا |
| "()[]{}" | true | أزواج ورا بعض: الـ stack بيفضى ويتملي |
Complexity: كل حرف بيعمل push أو pop مرة واحدة، فـ O(n) time. والـ space O(n) في الـ worst case، لما يكون كله openers.
if (s.length % 2 === 1) return false; في الأول. مش بيغيّر الـ complexity، بس بيوري الـ interviewer إنك بتفكر في الـ edge cases.
هنا الـ stack شايل العنصر نفسه بس. طب لو محتاج كل مستوى في الـ stack يفتكر معلومة زيادة؟
مثال محلول 2: Min Stack
الجديد هنا إن الـ stack مش بيشيل العنصر بس: كل مستوى بيشيل جنبه معلومة محسوبة وقت الـ push.
صمّم stack فيه العمليات العادية push و pop و top، وكمان getMin اللي بترجّع أصغر رقم موجود في الـ stack دلوقتي. كل العمليات لازم تبقى O(1).
نفكّر فيها مع بعض
- Brute force:
getMinتلف على الـ stack كله، O(n)، والمطلوب O(1). - متغير واحد
min؟ الـ push تمام. بس لو عملت pop للـ min نفسه، مين الـ min الجديد؟ المتغير مش فاكر، فهترجع تلف O(n). - الـ key insight: الـ stack بيتغيّر من فوق بس، فاللي تحت عمره ما بيتأثر باللي فوق. لو كل مستوى فاكر الـ min من تحت لحد عنده، أي pop بيسيب تحته إجابة جاهزة.
- الخطة: stack تاني اسمه
minsماشي جنب الأولاني خطوة بخطوة، وmins[i]= أصغر رقم فيstack[0..i]. - Edge cases: أول push، min متكرر، وأرقام سالبة.
- اتنين stacks بنفس الطول دايمًا. ده الـ invariant:
mins[i]= الـ min من تحت خالص لحد المستوىi. - الرقم نفسه بيدخل الـ stack العادي زي أي stack.
- الـ min الجديد = الأصغر بين الرقم والـ min اللي تحته. والشرط
mins.length === 0عشان أول push، لأنMath.min(5, undefined)بتطلعNaNوتبوّظ كل اللي بعدها. - بنعمل push للـ min حتى لو ما اتغيرش، عشان كل مستوى يبقى ليه خانة، والـ pop يشيل من الاتنين من غير ما يفكر.
- pop من الاتنين مع بعض. الـ min بتاع المستوى ده بيخرج معاه، واللي تحته هو الإجابة الصح على طول.
- top عادي: آخر خانة في
stack. - آخر خانة في
mins. O(1) لأنها اتحسبت وقت الـ push، مش وقت السؤال.
الاتنين مرسومين أفقي فوق بعض، عشان كل مستوى يبان قصاد الـ min بتاعه (الخانة 0 تحت خالص). و single var min هو اللي كان هيحصل لو استخدمنا متغير واحد:
<=
ممكن تعمل push في mins بس لما الرقم <= الـ min الحالي، وتعمل منه pop بس لما الطالع يساوي الـ min. لازم <= مش <: جرّب push(0)، push(1)، push(0)، pop() بـ <، هتلاقي getMin() بقت undefined والـ stack لسه فيه 0.
Complexity: كل operation O(1)، و O(n) space زيادة لـ mins. وفيه variant تالت بـ stack واحد فيه أزواج [val, minSoFar]، نفس الفكرة بالظبط.
لحد دلوقتي بنعمل push لحاجات جاية من الـ input. طب لو الـ stack بيشيل نتايج بنحسبها ونرجّعها فيه تاني؟
مثال محلول 3: Evaluate Reverse Polish Notation
الجديد هنا إن الـ stack بيشيل نتايج متوسطة: بنعمل pop لاتنين، نحسب، ونعمل push للناتج تاني. وكمان ترتيب الـ pop بقى بيفرق.
عندك expression مكتوبة بطريقة Reverse Polish Notation: الـ operator بييجي بعد الرقمين بتوعه. مثلًا 2 + 3 بتتكتب 2 3 +. الـ tokens جاية في array من strings، والعمليات + - * /، والقسمة بتشيل الكسر ناحية الصفر. احسب الناتج.
نفكّر فيها مع بعض
- يعني إيه RPN؟ بدل
7 / (2 - 5)بتكتب7 2 5 - /. مفيش أقواس خالص، لأن كل operator بياخد آخر رقمين ظهروا قبله. - آخر رقمين = اللي فوق في stack. الأرقام تستنى في الـ stack، والـ operator ياخد اتنين من فوق ويرجّع الناتج مكانهم، لأن الناتج ممكن يبقى operand لـ operator جاي.
- الترتيب: في
["4","3","-"]أول pop بيطلّع 3، وده الرقم اليمينb. التاني بيطلّع 4، ودهa. الناتجa - b = 1، ولو عكست هتطلع -1. - القسمة ناحية الصفر:
-4.5تبقى-4مش-5، ودهMath.trunc. - Edge cases: token واحد بس، رقم سالب زي
"-11"(ده رقم مش operator)، وقسمة ناتجها بين -1 و 0.
- الـ stack فيه الأرقام اللي مستنية operator.
- مقارنة كاملة بـ
===، مشt[0] === '-'، عشان"-11"رقم سالب وبيبدأ بـ-. - أول pop هو الرقم اليمين، لأنه آخر واحد دخل. سمّيناه
bعشان نكتبa - bبنفس ترتيب القراية. - ليه سطرين منفصلين؟
stack.pop() - stack.pop()بتتنفّذ من الشمال، فـbهيبقى على الشمال والناتجb - a. - الناتج بيرجع الـ stack لأنه ممكن يبقى operand في عملية جاية.
- JS مفيهاش integer division، فـ
7 / -3بتطلع-2.333، وMath.truncبتشيل الكسر:-2. أماMath.floorفبتقرّب ناحية سالب ما لا نهاية (-3)، والـ bug ده مش بيبان غير لما الناتج يبقى سالب. - مش operator يبقى رقم. من غير
Number،"2" + "3"هتبقى"23". - الـ expression الصح بيخلص وفي الـ stack رقم واحد بالظبط.
القسمة ناحية الصفر في JS: كل الطرق
| القسمة | الناتج الحقيقي | Math.trunc | Math.floor | (a / b) | 0 | parseInt(a / b) |
|---|---|---|---|---|---|
| 7 / 2 | 3.5 | 3 | 3 | 3 | 3 |
| -7 / 2 | -3.5 | -3 | -4 ✗ | -3 | -3 |
| 7 / -3 | -2.333 | -2 | -3 ✗ | -2 | -2 |
| 6 / -132 | -0.045 | -0 (= 0) | -1 ✗ | 0 | -0 (= 0) |
| 1 / 30000000 | 3.3e-8 | 0 | 0 | 0 | 3 ✗ |
| 3000000000 / 1 | 3000000000 | 3000000000 | 3000000000 | -1294967296 ✗ | 3000000000 |
| 0بيحوّل لـ 32-bit integer، فبيقطع ناحية الصفر صح، بس أي رقم أكبر من حوالي 2.1 مليار بيبوظ. هنا الـ constraints جوه 32-bit فهتعدّي، بس ليه تخاطر.parseIntمعمولة للـ strings: الرقم الصغير جدًا بيتحوّل الأول لـ"3.3333333333333334e-8"، فبتقرا الـ 3 وتقف عند النقطة.-0:Math.trunc(-0.045)بتطلع-0، بس-0 === 0بـ true وبيتطبع 0، فمش مشكلة.
Complexity: كل token بيعمل push مرة و pop مرة بالكتير: O(n) time و O(n) space.
في كل اللي فات، الـ stack بيرجّعلك آخر حاجة وخلاص. طب لو عايز لكل عنصر "أول رقم أكبر منه على يمينه"؟ هنا بييجي الـ monotonic stack.
Monotonic Stack: أول رقم أكبر مني
المسألة الأم: لكل رقم في array، هات أول رقم أكبر منه على يمينه، ولو مفيش يبقى -1. مثلًا [4, 2, 1, 3, 6, 5] إجابتها [6, 3, 3, 6, -1, -1].
ده O(n²)، والـ worst case لما الأرقام بتقل زي [9, 8, 7, ..., 1]: كل رقم بيلف للآخر على الفاضي.
الـ key insight: امشي من الشمال لليمين، وأي رقم لسه ما لقاش إجابته خليه مستني في stack. لما رقم جديد ييجي، هو الإجابة لكل المستنيين الأصغر منه. والحلو إن المستنيين دايمًا مترتبين:
- لو
xمستني وجه بعدهyأكبر منه،xبيخرج على طول. فعمر ما رقم يفضل مستني تحت رقم أكبر منه جه بعده. - يعني الـ stack من تحت لفوق متناقص. ده الـ invariant، ومنه جه اسم monotonic.
- فالأصغر من الرقم الجديد هم بالظبط اللي فوق. بنعمل pop لحد أول واحد مش أصغر ونقف، لأن كل اللي تحته أكبر منه.
fill(-1): اللي مش هيلاقي أكبر منه هيفضل -1 من غير أي شغل زيادة في الآخر.- الـ stack فيه indices مش values. الأسباب تحت الـ animation.
- one pass من الشمال لليمين، كل index بيتزار مرة.
- ليه
whileمشif؟ رقم واحد ممكن يبقى الإجابة لكذا واحد مستني (الـ 3 حلّت الـ 1 والـ 2). وstack.length > 0الأول عشان الـ&&تقف قبل ما تقراstack[-1]. و>مش>=لأن المساوي مش "أكبر". jلقى إجابته حالًا، وهيnums[i]. محتاجين الـ index عشان نعرف نكتبها فين فيres.iنفسه يدخل يستنى. وبما إن كل الأصغر منه خرجوا، الـ invariant (متناقص) لسه ماشي.- اللي فضلوا في الـ stack مالهمش إجابة، وقيمتهم -1 من سطر 2.
خانات الـ stack مكتوبة index:value للتوضيح بس، المتخزّن فعلًا هو الـ index. والخانات المتقطّعة في nums هي المستنية:
ليه indices مش values؟
- عشان تعرف تكتب فين:
res[j] = ...محتاجةj. - ساعات المطلوب مسافة: "بعد كام يوم؟" =
i - j، والقيمة لوحدها مش هتديك ده. - التكرار: في
[2, 5, 2]القيمة 2 مش بتقولك أنهي 2. ومن الـ index تقدر دايمًا تجيب القيمة، إنما العكس مش مضمون.
| المطلوب | الـ stack من تحت لفوق | الـ while بتعمل pop لما | الإجابة بتتكتب إمتى |
|---|---|---|---|
| أول أكبر على اليمين | متناقص | nums[i] > nums[top] | للي بيعمل pop: إجابته nums[i] |
| أول أصغر على اليمين | متزايد | nums[i] < nums[top] | للي بيعمل pop: إجابته nums[i] |
| أول أكبر على الشمال | متناقص | nums[top] <= nums[i] | لـ i بعد الـ while: الـ top لو موجود |
| أول أصغر على الشمال | متزايد | nums[top] >= nums[i] | لـ i بعد الـ while: الـ top لو موجود |
القاعدة: بتدوّر على أكبر؟ stack متناقص. بتدوّر على أصغر؟ متزايد.
الـ template جاهز. أسهل استخدام ليه: نفس السؤال، بس جاي لأرقام معيّنة وبالقيمة.
مثال محلول 4: Next Greater Element I
الجديد هنا إن الأسئلة جاية بالقيمة لأرقام معيّنة، فبنحسب الإجابة لكل الأرقام مرة واحدة ونحطها في Map.
عندك array اسمها nums2 أرقامها كلها مختلفة، و nums1 فيها شوية من أرقام nums2. لكل رقم في nums1، دوّر عليه في nums2، وهات أول رقم أكبر منه على يمينه هناك. لو مفيش، -1.
نفكّر فيها مع بعض
- Brute force: لكل رقم في
nums1، دوّر عليه فيnums2وبعدين على يمينه:O(n1 × n2). - الـ key insight: احسب "أول أكبر" لكل
nums2في one pass بالـ template، وخزّنه في Map. وبعدين كل سؤال يبقى lookup في O(1). - Map بالقيمة ليه؟ السؤال جاي بالقيمة مش بالـ index، والأرقام مختلفة، فكل قيمة ليها مكان واحد.
- والـ stack هنا ممكن يشيل values: المطلوب قيمة مش مسافة، ومفيش تكرار. دي الحالة الوحيدة اللي الـ indices فيها مش لازمة.
- Edge cases: أكبر رقم في
nums2وآخر رقم فيها: الاتنين ممكن مالهمش إجابة.
- Map: رقم من
nums2← أول أكبر منه. اللي مالوش إجابة مش هيدخل الـ Map أصلًا. - values مش indices، لأن الأرقام مختلفة والمطلوب القيمة نفسها.
for...ofلأننا مش محتاجين index في أي حتة.- نفس الـ template بالظبط.
next.set(stack.pop(), x)بتعمل pop وتسجّل في خطوة واحدة. xيستنى أول أكبر منه.- موجود في الـ Map يبقى ليه إجابة، مش موجود يبقى -1. استخدم
hasمشnext.get(v) || -1، لأن لو الإجابة 0 الـ||هيقلبها -1.
Complexity: O(n1 + n2) time، و O(n2) space للـ Map والـ stack.
هنا الإجابة قيمة. طب لو المطلوب "بعد كام خطوة"؟ ساعتها الـ values مش هتكفي.
مثال محلول 5: Daily Temperatures
الجديد هنا إن الإجابة مسافة مش قيمة، فالـ indices بقت لازمة.
عندك درجة الحرارة لكل يوم. لكل يوم، عايز تعرف هتستنى كام يوم لحد ما ييجي يوم أدفى منه. لو مفيش يوم أدفى بعده خالص، الإجابة 0.
نفكّر فيها مع بعض
- افهم المطلوب: "أول أكبر على اليمين" بالظبط، بس الإجابة
i - jمشtemps[i]. - Brute force: لكل يوم دوّر قدّام، O(n²). والـ worst case لما الحرارة بتقل كل يوم.
- الـ key insight: نفس الـ template، والـ stack فيه indices الأيام المستنية. لو خزّنت درجات الحرارة بس، هتعرف مين مستني بس مش من إمتى.
- الفرق الوحيد: الـ default بقى 0 مش -1.
- Edge cases: يوم واحد، حرارة ثابتة (المساوي مش أدفى)، كلها بتزيد، وكلها بتقل.
fill(0)، لأن المسألة قالت لو مفيش يوم أدفى الإجابة 0.- indices الأيام المستنية، وحرارتهم من تحت لفوق متناقصة أو متساوية.
<مش<=: آخر index هوlength - 1، وtemps[length]هتبقىundefined.>لأن "أدفى" يعني أكبر، واليوم المساوي مش إجابة (شوف[50, 50, 50]في الجدول تحت).- الانتظار
i - jمشi - j + 1: من يوم 1 ليوم 5 بتستنى 4 أيام. ده مسافة بين يومين، مش عدد عناصر في range. - اليوم الحالي يستنى يوم أدفى منه.
- الأيام اللي فضلت في الـ stack إجابتها 0 من سطر 2.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [70] | [0] | يوم واحد: push ومفيش pop |
| [30, 40, 50, 60] | [1, 1, 1, 0] | كل يوم بيعمل pop للي قبله، والـ stack عمره ما يعدّي عنصر |
| [60, 50, 40, 30] | [0, 0, 0, 0] | مفيش pop خالص، كله مستني |
| [50, 50, 50] | [0, 0, 0] | بـ >= هتطلع [1, 1, 0] |
| [30, 20, 10, 40] | [3, 2, 1, 0] | الـ 40 بتعمل pop لتلات أيام مرة واحدة، وده سبب الـ while |
Complexity: O(n) time (نفس حسبة الـ amortized فوق)، و O(n) space في الـ worst case لما الحرارة بتقل كل يوم. وفي الانترفيو قول حسبة الـ amortized دي قبل ما تتسأل عليها.
لحد هنا بندوّر على أول أكبر من ناحية واحدة. طب لو محتاج أول أصغر من الناحيتين في نفس اللحظة؟
مثال محلول 6 (hard اختياري): Largest Rectangle in Histogram
الجديد هنا إن الـ stack متزايد، ولحظة الـ pop بتديك الحدّين مع بعض: i هو الحد اليمين، واللي تحت في الـ stack هو الحد الشمال. المسألة hard واختيارية، فلو اتشبعت، اقفز للـ call stack وارجعلها بعدين.
عندك أعمدة جنب بعض، عرض كل عمود 1 وارتفاعه heights[i]. هات مساحة أكبر مستطيل تقدر ترسمه جوه الأعمدة دي. المستطيل قاعد على الأرض، وارتفاعه ما ينفعش يعدّي أقصر عمود تحته.
نفكّر فيها مع بعض
- Brute force: لكل range، المساحة = أقصر عمود × العرض: O(n²)، و
nلحد 10⁵. - اقلب السؤال: لكل عمود: "لو هو أقصر عمود في المستطيل، يتمد لحد فين؟". لحد أول أقصر منه يمين، وأول أقصر منه شمال.
- الـ key insight: في stack متزايد، لما عمود يعمل pop بسبب
i، يبقىiأول أقصر منه يمين، واللي تحته في الـ stack أول أقصر منه شمال. - العرض: الأعمدة اللي بين الحدّين من غيرهم:
i - left - 1. - الأعمدة اللي هتفضل في الآخر: عمود وهمي ارتفاعه 0 عند
i = nبيعمل pop لكلهم.
- indices، والارتفاعات من تحت لفوق متزايدة، لأننا بندوّر على أول أصغر.
best = 0لأن أقل مساحة ممكنة صفر.- هنا
<=مقصودة: اللفة الزيادة عندi = nهي العمود الوهمي. بـ<، الـ[1, 2, 3]هتطلع 0 بدل 4 لأن مفيش ولا pop. heights[n]=undefined، فبنستخدم 0 بدلها، والـ 0 أقصر من الكل فبيفضّي الـ stack.- العمود الجديد أقصر من اللي فوق، فاللي فوق اتقفل من اليمين. المتساوي بنسيبه، لأن آخر واحد في المتساويين هيحسب العرض كله (و
<=بتدّي نفس الإجابة برضه). topهو أقصر عمود في المستطيل اللي بنحسبه.leftهو اللي تحته، أول أقصر منه شمال. لو الـ stack فضي يبقى الحد-1مش0، لأن الحد نفسه مش داخل والعمود 0 داخل.- الأعمدة من
left + 1لـi - 1، وعددهم(i - 1) - (left + 1) + 1 = i - left - 1. - المساحة = ارتفاع
top× العرض. - العمود الحالي يدخل، والـ stack لسه متزايد.
فوق: الأعمدة مرسومة خانات، والمستطيل اللي بيتحسب بالأزرق. تحت: الـ array ومعاها العمود الوهمي:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [5] | 5 | عمود واحد: مش بيعمل pop غير عند العمود الوهمي |
| [3, 3, 3] | 9 | متساويين: آخر واحد بيحسب العرض كله |
| [1, 2, 3, 4, 5] | 9 | متزايدة: من غير العمود الوهمي الإجابة 0 |
| [5, 4, 3, 2, 1] | 9 | متناقصة: كل عمود بيعمل pop للي قبله |
| [0, 0] | 0 | best بتبدأ من 0 |
Complexity: كل index (ومعاهم الوهمي) بيعمل push مرة و pop مرة بالكتير: O(n) time و O(n) space.
الـ stack ده إنت اللي بتديره بإيدك. طب تعرف إن فيه stack تاني شغال في كل برنامج من غير ما تشوفه؟
الـ Call Stack: الـ stack اللي جوه كل برنامج
كل ما function تنادي function تانية، JS لازم تفتكر الأولانية كانت واقفة فين ومتغيراتها قيمتها إيه. الحاجات دي بتتحط في frame، والـ frames فوق بعض في stack اسمه call stack: آخر function اتنادت هي أول واحدة تخلص.
وده بيبان أوضح ما يكون لما function تنادي نفسها، يعني recursion:
- كل نداء بيعمل frame جديد فوق، وكل frame عنده نسخته من
n، فالـ 3 بتاعةsumTo(3)ما حدّش بيبوّظها وهي مستنية. - آخر نداء (
sumTo(0)) هو أول واحد رجع: LIFO بالظبط. - Valid Parentheses نفس الفكرة: كل قوس مفتوح زي function اتنادت ولسه ما رجعتش.
sumTo بتقع عند حوالي 10 آلاف نداء جوه بعض، و sumTo(1000000) بتدّي RangeError: Maximum call stack size exceeded. الحل ساعتها stack بإيدك (array عادية) بدل الـ recursion، وهتشوفه في الـ DFS.
ده تمهيد بس، والتفاصيل كلها في فصل Recursion.
شفت كام مكان سطر واحد ممكن يغلّطك فيه؟ يلا نجمعهم.
غلطات مشهورة
كل الغلطات دي بتعدّي من غير error في JS: الكود بيشتغل والإجابة غلط، وده اللي بيخلّيها خطيرة.
1. peek بـ stack[stack.length]
الصح stack[stack.length - 1] أو stack.at(-1). نفس غلطة i <= n: الـ indices بتقف عند length - 1.
2. نسيت تشيك إن الـ stack فضي في الآخر
الصح return stack.length === 0;.
3. عكست ترتيب الـ operands
خزّن أول pop في b، والتاني في a، وبعدين احسب a - b. ونفس الكلام في القسمة.
4. Math.floor أو parseInt للقسمة ناحية الصفر
الصح Math.trunc(a / b).
5. if بدل while في الـ monotonic stack
الـ 40 أدفى من التلات أيام اللي قبلها، والـ if بتحل واحد بس. الـ while بتكمّل لحد ما الـ top يبقى مش أصغر أو الـ stack يفضى، والصح [3, 2, 1, 0].
6. خزّنت values بدل indices
خزّن i، وهات الحرارة وقت ما تحتاجها بـ temps[stack[stack.length - 1]].
دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.
اختبر نفسك
على stack فاضي عملت: push(1)، push(2)، pop()، push(3)، push(4)، pop()، pop(). آخر pop() رجّعت إيه؟
- 1
- 2
- 3
- 4
بعد أول تلات عمليات الـ stack فيه [1]، وبعد push(3)، push(4) بقى [1, 3, 4]. أول pop بتطلّع 4، والتانية 3.
إيه الـ input اللي بيخلّي حل الـ counter يقول true، والـ stack يقول false؟
"(()""))((""([)]"""
"(()" الـ counter بيخلص بـ 1، و "))((" بيبقى سالب من أول حرف، فالاتنين false صح. "" الاتنين true. أما "([)]" فالـ counter بيخلص بصفر والترتيب غلط، والـ stack بس هو اللي بيشوف الترتيب.
ناتج ["3","8","-","2","/"] كام؟
- -3
- -2
- 2
- 2.5
a = 3 و b = 8، فـ 3 - 8 = -5. بعدها -5 / 2 = -2.5، وناحية الصفر -2. الـ -3 إجابة Math.floor، والـ 2 إجابة اللي عكس الترتيب.
الـ monotonic stack فيه while جوه for. الـ time complexity كام؟
- O(n)، لأن كل index بيعمل push مرة و pop مرة بالكتير
- O(n²)، لأن فيه loop جوه loop
- O(n log n)
- O(n) بس لو الـ array مترتبة
عدد الـ pops في كل اللفّات على بعض مش ممكن يعدّي عدد الـ pushes، وده n بالظبط. فالمجموع 2n بالكتير، مهما كان شكل الـ array.
في Min Stack، عملنا pop() لرقم مش هو الـ min. ليه لسه لازم نعمل pop من mins؟
- مش لازم، ممكن نسيبه
- عشان
mins[i]مربوط بالمستوىi، والاتنين لازم يفضلوا بنفس الطول - عشان نوفّر memory بس
- عشان الـ min اتغيّر
كل خانة في mins معناها "الـ min لو الـ stack واقف هنا". لو سبتها، آخر خانة هتتكلم عن مستوى مش موجود، و getMin هترجّع إجابة قديمة.
في Daily Temperatures، لو كتبت >= بدل > في الـ while، [50, 50, 50] هتطلع إيه؟
[0, 0, 0][1, 1, 0][2, 1, 0][1, 1, 1]
كل 50 هتعمل pop للـ 50 اللي قبلها وتكتب 1، والأخيرة بتفضل 0. بس 50 مش أدفى من 50، فالصح [0, 0, 0].
تمرين: فكّر قبل ما تفتح
نفس "أول أكبر على اليمين"، بس الـ array دايرية: بعد آخر عنصر بترجع لأول عنصر. والأرقام ممكن تتكرر. لو مفيش أكبر، -1.
تلميح 1
تخيّل الـ array متكررة مرتين ورا بعض: [3, 8, 4, 1, 2, 3, 8, 4, 1, 2]. أي رقم إجابته "بعد اللفة" هيلاقيها في النسخة التانية.
تلميح 2
مش لازم تنسخ: لف i من 0 لـ 2n - 1 واستخدم nums[i % n]. اعمل push بس في اللفة الأولى (i < n)، وخزّن indices عشان التكرار.
الحل
ليه لفّتين بس؟ إجابة أي عنصر (لو موجودة) على بُعد أقل من n خطوة منه، فلفة تانية كاملة بتغطّي أي بُعد. و i < 2 * n مش <= لأن آخر index هو 2n - 1. والـ push في اللفة التانية مش هيبوّظ حاجة، بس ملوش لازمة. الـ complexity O(n).
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
حلها بالترتيب ده، كل مسألة بتضيف فكرة واحدة جديدة. علّم على اللي خلّصته، والتقدّم بيتحفظ. لو قعدت أكتر من 25 دقيقة على مسألة، ارجع للـ template بتاعها هنا، وبعدين حاول تاني من غير ما تبص.
- Valid Parenthesesالمثال المحلول 1. اكتبه من دماغك من غير ما تبص.
- Remove All Adjacent Duplicates In Stringقارن كل حرف بالـ top: لو زيه pop، لو لأ push. والـ stack في الآخر هو الإجابة.
- Backspace String Comparesimulation: الـ
#بتعمل pop. وبعدها فكّر في حل O(1) memory بـ two pointers من الآخر. - Min Stackالمثال المحلول 2: stack تاني بيفتكر الـ min لكل مستوى.
- Evaluate Reverse Polish Notationالمثال المحلول 3. خلي بالك من ترتيب الـ pop و
Math.trunc. - Simplify Pathقسّم بالـ
/. الـ..بتعمل pop، والـ.والفاضي بيتفوّتوا، والباقي push. - Decode Stringأقواس جوه أقواس: عند
[احفظ الشغل الحالي في stack، وعند]رجّعه. أول مرة تحفظ "state" مش حرف. - Next Greater Element Iالمثال المحلول 4: أول monotonic stack ليك، ومعاه Map.
- Daily Temperaturesالمثال المحلول 5: indices عشان المسافة
i - j. - Next Greater Element IIالتمرين اللي فوق: لفّتين و
i % n. - Online Stock Spanأول أكبر على الشمال، والأرقام جاية واحد واحد. خزّن أزواج
[price, span]. - Car Fleetsort بالمكان الأول، وبعدين stack بأوقات الوصول.
- Largest Rectangle in Histogramالمثال المحلول 6: stack متزايد، والعمود الوهمي، و
i - left - 1. - Trapping Rain Waterاختياري: حلّيتها بـ two pointers؟ حلها تاني بـ monotonic stack، كل pop بيقفل "حوض" مية.
وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.
الخلاصة
| السؤال | الإجابة |
|---|---|
| peek إزاي؟ | stack[stack.length - 1] أو stack.at(-1). مش stack[stack.length]. |
| pop على stack فاضي؟ | بترجّع undefined من غير error. شيك على length الأول. |
| القسمة ناحية الصفر؟ | Math.trunc(a / b)، مش Math.floor ولا parseInt. |
| values ولا indices؟ | indices، إلا لو المطلوب قيمة ومفيش تكرار (زي Next Greater Element I). |
| متناقص ولا متزايد؟ | بتدوّر على أكبر: متناقص. على أصغر: متزايد. |
while ولا if؟ | while: رقم واحد ممكن يحل كذا واحد مستني. |
> ولا >=؟ | "أكبر" بس يبقى >. المساوي مش إجابة. |
| Complexity؟ | O(n) time و O(n) space، حتى مع الـ while جوه الـ for. |
الفصل الجاي: Queue و Deque هو العكس: أول حاجة دخلت هي أول حاجة تطلع (FIFO)، زي طابور العيش. هتعرف ليه shift() اللي حذّرناك منها هنا بطيئة، وإزاي تعمل queue سريع في JS، وهتقابل الـ monotonic deque، ابن عم الـ monotonic stack اللي بيشيل من الناحيتين. وبعدها بشوية، فصل Recursion هيوريك الـ call stack من جوه.