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.

تشبيه رصّة الأطباق في المطبخ: بتحط الطبق فوق، وبتاخد من فوق، وعمرك ما بتسحب من تحت. آخر طبق دخل هو أول طبق يطلع، وده اسمه LIFO: Last In, First Out. ونفس الكلام في Ctrl+Z.

الـ stack ليه تلات operations بس: push (حط فوق)، pop (شيل اللي فوق ورجّعه)، و peek (بص على اللي فوق من غير ما تشيله). مفيش access للنص، والقيد ده هو بالظبط اللي بيخلّي كل operation O(1).

أشهر stack قدامك كل يوم هو زرار Back في الـ browser:

Back مرتين طلّع leetcode وبعدين youtube، يعني بعكس ترتيب الدخول بالظبط. ده الـ stack كله.

طب إزاي تعرف من كلام المسألة إن الحل stack أصلًا؟ ده الجزء الجاي.

إزاي تعرفه من المسألة

الـ stack بيظهر لما يبقى فيه حاجات مستنية، والأحدث فيهم هو اللي يتعامل الأول. الكلمات دي بتقولك إنه غالبًا stack:

لما تشوف: valid parenthesesbracketsnestedmatching pairs undobackspaceremove adjacent duplicatessimplify path evaluate expressionpostfix / RPNdecode string next greaternext smallerprevious greaterdays until warmerstock spanlargest rectangle
ومش هو غالبًا لو: first come, first servedlevel by level / shortest pathsliding window maximumk-th largest / top k

"أول واحد جه أول واحد يتخدم" ده 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 بياخد آخر رقمينأرقام مستنية operatorEvaluate 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.

  1. const بتمنع إن stack يشاور على array تانية، مش بتمنع التعديل. فـ push و pop شغالين عادي.
  2. push بتحط في آخر الـ array، يعني فوق. الـ 2 دخلت آخر واحدة، فهي اللي هتطلع الأول.
  3. peek. ليه - 1؟ الطول 3 والـ indices هي 0 و 1 و 2، فآخر index هو length - 1. ولو كتبت stack[stack.length] هترجع undefined من غير أي error، و stack.at(-1) بديل صح.
  4. pop بتشيل آخر عنصر وبترجّعه. O(1) لأن مفيش ولا عنصر تاني اتحرك.
  5. isEmpty. هتكتب الشرط ده قبل أي pop أو peek تقريبًا.
  6. ترتيب الخروج (2 ثم 8 ثم 5) عكس ترتيب الدخول (5 ثم 8 ثم 2).
  7. خلي بالك: pop على stack فاضي في JS مش بيضرب error، بيرجّع undefined بهدوء (Java و Python بيرموا exception). فالـ bug بيبان بعدين في مكان تاني، وعشان كده اتعوّد تشيك على length الأول.
الـ operationفي JSالوقتملاحظة
pushstack.push(x)O(1) amortizedشرحها تحت
popstack.pop()O(1)بترجّع undefined لو فاضي
peekstack[stack.length - 1]O(1)أو stack.at(-1)
isEmpty / sizestack.lengthO(1)
searchstack.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

Valid Parentheses

easyLeetCode 20

عندك string كله أقواس من الأنواع () و [] و {}. هل كل قوس اتفتح اتقفل بنفس نوعه، وبالترتيب الصح، يعني اللي اتفتح جوه يتقفل الأول؟

Input: "{[()]()}" → true Input: "([)]" → false (the [ must close before the )) Input: "((" → false (opened, never closed) Input: ")" → false (closed, never opened)

نفكّر فيها مع بعض

  1. افهم المطلوب: كل closer ليه opener من نوعه، والـ opener ده لازم يكون آخر واحد لسه مفتوح، ومفيش حاجة تفضل مفتوحة في الآخر.
  2. Brute force: شيل أي () أو [] أو {} جنب بعض وكرّر. شغال، بس ممكن تحتاج n/2 لفة كل واحدة O(n)، يعني O(n²).
  3. الـ key insight: الـ closer لازم يقابل آخر opener لسه مفتوح، و"آخر واحد" ده هو الـ top.
  4. الخطة: opener يعمل push. closer: الـ stack لازم ما يبقاش فاضي، والـ pop يطلّع نفس النوع. وفي الآخر الـ stack لازم يبقى فاضي.
  5. Edge cases: string فاضي (true)، ")"، "(("، وطول فردي (أكيد false).
  1. الـ map من الـ closer للـ opener، مش العكس. لحظة ما تقابل closer، هو اللي في إيدك، وهو اللي بتسأل بيه: "مين المفروض يكون فوق؟".
  2. الـ stack فيه الـ openers اللي لسه مفتوحة، بترتيب فتحها.
  3. for...of على الحروف على طول، فمفيش index ولا قلق < و <=.
  4. opener: لسه مش هنعرف هو صح ولا لأ، فيستنى الـ closer بتاعه في الـ stack.
  5. closer والـ stack فاضي، يعني بنقفل حاجة ما اتفتحتش. في JS السطر ده ممكن يتشال لأن pop() هترجّع undefined والشرط اللي بعده هيفشل، بس اكتبه صريح: أوضح، وفي C++ الـ top() على stack فاضي undefined behavior.
  6. pop ومقارنة في سطر واحد. لو اللي طلع مش الـ opener المطلوب، يبقى النوع أو الترتيب غلط، فبنعمل early return.
  7. ليه مش return true؟ "((" عمرها ما دخلت الـ else، فهتطلع true غلط. أي حاجة فاضلة في الـ stack هي opener ما اتقفلش.

الخانات الخضرا في الـ string هي الأزواج اللي اتقفلت:

ودي الحالة اللي الـ counter غلط فيها. الـ stack بيمسكها عند أول closer:

Inputالمتوقعليه الحالة دي مهمة
""trueالـ loop مش بتلف، والـ stack فاضي
"("falseفاضل opener، والسطر 12 بيمسكها
")"falsecloser والـ stack فاضي، السطر 8
"(("falsereturn true في الآخر هتطلّعها غلط
"([)]"falseالـ counter بيقول true هنا
"()[]{}"trueأزواج ورا بعض: الـ stack بيفضى ويتملي

Complexity: كل حرف بيعمل push أو pop مرة واحدة، فـ O(n) time. والـ space O(n) في الـ worst case، لما يكون كله openers.

Early exit طول فردي معناه أكيد فيه قوس مالوش زوج: if (s.length % 2 === 1) return false; في الأول. مش بيغيّر الـ complexity، بس بيوري الـ interviewer إنك بتفكر في الـ edge cases.

هنا الـ stack شايل العنصر نفسه بس. طب لو محتاج كل مستوى في الـ stack يفتكر معلومة زيادة؟

مثال محلول 2: Min Stack

الجديد هنا إن الـ stack مش بيشيل العنصر بس: كل مستوى بيشيل جنبه معلومة محسوبة وقت الـ push.

Min Stack

mediumLeetCode 155

صمّم stack فيه العمليات العادية push و pop و top، وكمان getMin اللي بترجّع أصغر رقم موجود في الـ stack دلوقتي. كل العمليات لازم تبقى O(1).

push(5), push(2), push(4), push(1) getMin() → 1 pop() (removes 1) getMin() → 2 pop() (removes 4) top() → 2 getMin() → 2

نفكّر فيها مع بعض

  1. Brute force: getMin تلف على الـ stack كله، O(n)، والمطلوب O(1).
  2. متغير واحد min؟ الـ push تمام. بس لو عملت pop للـ min نفسه، مين الـ min الجديد؟ المتغير مش فاكر، فهترجع تلف O(n).
  3. الـ key insight: الـ stack بيتغيّر من فوق بس، فاللي تحت عمره ما بيتأثر باللي فوق. لو كل مستوى فاكر الـ min من تحت لحد عنده، أي pop بيسيب تحته إجابة جاهزة.
  4. الخطة: stack تاني اسمه mins ماشي جنب الأولاني خطوة بخطوة، و mins[i] = أصغر رقم في stack[0..i].
  5. Edge cases: أول push، min متكرر، وأرقام سالبة.
  1. اتنين stacks بنفس الطول دايمًا. ده الـ invariant: mins[i] = الـ min من تحت خالص لحد المستوى i.
  2. الرقم نفسه بيدخل الـ stack العادي زي أي stack.
  3. الـ min الجديد = الأصغر بين الرقم والـ min اللي تحته. والشرط mins.length === 0 عشان أول push، لأن Math.min(5, undefined) بتطلع NaN وتبوّظ كل اللي بعدها.
  4. بنعمل push للـ min حتى لو ما اتغيرش، عشان كل مستوى يبقى ليه خانة، والـ pop يشيل من الاتنين من غير ما يفكر.
  5. pop من الاتنين مع بعض. الـ min بتاع المستوى ده بيخرج معاه، واللي تحته هو الإجابة الصح على طول.
  6. top عادي: آخر خانة في stack.
  7. آخر خانة في mins. O(1) لأنها اتحسبت وقت الـ push، مش وقت السؤال.

الاتنين مرسومين أفقي فوق بعض، عشان كل مستوى يبان قصاد الـ min بتاعه (الخانة 0 تحت خالص). و single var min هو اللي كان هيحصل لو استخدمنا متغير واحد:

Variant بيوفّر memory، وفخ الـ <= ممكن تعمل 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]، نفس الفكرة بالظبط.

في الانترفيو قول الفكرة في جملة: "كل مستوى بيفتكر الـ min وقت ما اتعمل، والـ stack بيتغيّر من فوق بس، فاللي تحت عمره ما بيبوظ". دي الجملة اللي بتفرّق بين حد حافظ وحد فاهم.

لحد دلوقتي بنعمل push لحاجات جاية من الـ input. طب لو الـ stack بيشيل نتايج بنحسبها ونرجّعها فيه تاني؟

مثال محلول 3: Evaluate Reverse Polish Notation

الجديد هنا إن الـ stack بيشيل نتايج متوسطة: بنعمل pop لاتنين، نحسب، ونعمل push للناتج تاني. وكمان ترتيب الـ pop بقى بيفرق.

Evaluate Reverse Polish Notation

mediumLeetCode 150

عندك expression مكتوبة بطريقة Reverse Polish Notation: الـ operator بييجي بعد الرقمين بتوعه. مثلًا 2 + 3 بتتكتب 2 3 +. الـ tokens جاية في array من strings، والعمليات + - * /، والقسمة بتشيل الكسر ناحية الصفر. احسب الناتج.

Input: ["7","2","5","-","/","1","+"] → -1 (7 / (2 - 5) + 1 = -2 + 1) Input: ["4","3","-"] → 1 (4 - 3, not 3 - 4) Input: ["-9","2","/"] → -4 (-4.5 cut toward zero)

نفكّر فيها مع بعض

  1. يعني إيه RPN؟ بدل 7 / (2 - 5) بتكتب 7 2 5 - /. مفيش أقواس خالص، لأن كل operator بياخد آخر رقمين ظهروا قبله.
  2. آخر رقمين = اللي فوق في stack. الأرقام تستنى في الـ stack، والـ operator ياخد اتنين من فوق ويرجّع الناتج مكانهم، لأن الناتج ممكن يبقى operand لـ operator جاي.
  3. الترتيب: في ["4","3","-"] أول pop بيطلّع 3، وده الرقم اليمين b. التاني بيطلّع 4، وده a. الناتج a - b = 1، ولو عكست هتطلع -1.
  4. القسمة ناحية الصفر: -4.5 تبقى -4 مش -5، وده Math.trunc.
  5. Edge cases: token واحد بس، رقم سالب زي "-11" (ده رقم مش operator)، وقسمة ناتجها بين -1 و 0.
  1. الـ stack فيه الأرقام اللي مستنية operator.
  2. مقارنة كاملة بـ ===، مش t[0] === '-'، عشان "-11" رقم سالب وبيبدأ بـ -.
  3. أول pop هو الرقم اليمين، لأنه آخر واحد دخل. سمّيناه b عشان نكتب a - b بنفس ترتيب القراية.
  4. ليه سطرين منفصلين؟ stack.pop() - stack.pop() بتتنفّذ من الشمال، فـ b هيبقى على الشمال والناتج b - a.
  5. الناتج بيرجع الـ stack لأنه ممكن يبقى operand في عملية جاية.
  6. JS مفيهاش integer division، فـ 7 / -3 بتطلع -2.333، و Math.trunc بتشيل الكسر: -2. أما Math.floor فبتقرّب ناحية سالب ما لا نهاية (-3)، والـ bug ده مش بيبان غير لما الناتج يبقى سالب.
  7. مش operator يبقى رقم. من غير Number، "2" + "3" هتبقى "23".
  8. الـ expression الصح بيخلص وفي الـ stack رقم واحد بالظبط.

القسمة ناحية الصفر في JS: كل الطرق

القسمةالناتج الحقيقيMath.truncMath.floor(a / b) | 0parseInt(a / b)
7 / 23.53333
-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 / 300000003.3e-80003 ✗
3000000000 / 1300000000030000000003000000000-1294967296 ✗3000000000

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. لما رقم جديد ييجي، هو الإجابة لكل المستنيين الأصغر منه. والحلو إن المستنيين دايمًا مترتبين:

تشبيه ناس قاعدين في صف، وكل واحد مستني أول حد أطول منه ييجي. اللي بييجي بيبص على آخر الصف: كل اللي أقصر منه هناك لقوا اللي مستنيينه ومشيوا. أول ما يقابل حد أطول يقف، ويقعد هو في آخر الصف. فالصف دايمًا من الأطول للأقصر.
  1. fill(-1): اللي مش هيلاقي أكبر منه هيفضل -1 من غير أي شغل زيادة في الآخر.
  2. الـ stack فيه indices مش values. الأسباب تحت الـ animation.
  3. one pass من الشمال لليمين، كل index بيتزار مرة.
  4. ليه while مش if؟ رقم واحد ممكن يبقى الإجابة لكذا واحد مستني (الـ 3 حلّت الـ 1 والـ 2). و stack.length > 0 الأول عشان الـ && تقف قبل ما تقرا stack[-1]. و > مش >= لأن المساوي مش "أكبر".
  5. j لقى إجابته حالًا، وهي nums[i]. محتاجين الـ index عشان نعرف نكتبها فين في res.
  6. i نفسه يدخل يستنى. وبما إن كل الأصغر منه خرجوا، الـ invariant (متناقص) لسه ماشي.
  7. اللي فضلوا في الـ stack مالهمش إجابة، وقيمتهم -1 من سطر 2.

خانات الـ stack مكتوبة index:value للتوضيح بس، المتخزّن فعلًا هو الـ index. والخانات المتقطّعة في nums هي المستنية:

ليه indices مش values؟

  1. عشان تعرف تكتب فين: res[j] = ... محتاجة j.
  2. ساعات المطلوب مسافة: "بعد كام يوم؟" = i - j، والقيمة لوحدها مش هتديك ده.
  3. التكرار: في [2, 5, 2] القيمة 2 مش بتقولك أنهي 2. ومن الـ index تقدر دايمًا تجيب القيمة، إنما العكس مش مضمون.
ليه O(n) مع إن فيه loop جوه loop؟ عدّ من ناحية العناصر مش اللفّات: كل index بيعمل push مرة واحدة بالظبط، و pop مرة واحدة بالكتير. فالمجموع 2n operations مهما كان شكل الـ array، يعني O(n). ده الـ amortized analysis: لفة ممكن تعمل pops كتير، بس على حساب لفّات تانية ما عملتش ولا pop.
المطلوبالـ 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.

Next Greater Element I

easyLeetCode 496

عندك array اسمها nums2 أرقامها كلها مختلفة، و nums1 فيها شوية من أرقام nums2. لكل رقم في nums1، دوّر عليه في nums2، وهات أول رقم أكبر منه على يمينه هناك. لو مفيش، -1.

Input: nums1 = [4, 1, 7], nums2 = [1, 6, 3, 4, 2, 7] Output: [7, 6, -1] (4 in nums2: first bigger to its right is 7. 1: it is 6. 7: nothing.)

نفكّر فيها مع بعض

  1. Brute force: لكل رقم في nums1، دوّر عليه في nums2 وبعدين على يمينه: O(n1 × n2).
  2. الـ key insight: احسب "أول أكبر" لكل nums2 في one pass بالـ template، وخزّنه في Map. وبعدين كل سؤال يبقى lookup في O(1).
  3. Map بالقيمة ليه؟ السؤال جاي بالقيمة مش بالـ index، والأرقام مختلفة، فكل قيمة ليها مكان واحد.
  4. والـ stack هنا ممكن يشيل values: المطلوب قيمة مش مسافة، ومفيش تكرار. دي الحالة الوحيدة اللي الـ indices فيها مش لازمة.
  5. Edge cases: أكبر رقم في nums2 وآخر رقم فيها: الاتنين ممكن مالهمش إجابة.
  1. Map: رقم من nums2 ← أول أكبر منه. اللي مالوش إجابة مش هيدخل الـ Map أصلًا.
  2. values مش indices، لأن الأرقام مختلفة والمطلوب القيمة نفسها.
  3. for...of لأننا مش محتاجين index في أي حتة.
  4. نفس الـ template بالظبط. next.set(stack.pop(), x) بتعمل pop وتسجّل في خطوة واحدة.
  5. x يستنى أول أكبر منه.
  6. موجود في الـ Map يبقى ليه إجابة، مش موجود يبقى -1. استخدم has مش next.get(v) || -1، لأن لو الإجابة 0 الـ || هيقلبها -1.

Complexity: O(n1 + n2) time، و O(n2) space للـ Map والـ stack.

Pattern بيتكرر "احسب لكل العناصر مرة واحدة وخزّن في Map، وبعدين جاوب بـ lookup" ده نفس اللي عملته في Hash Map، بس المرة دي الحساب جاي من monotonic stack.

هنا الإجابة قيمة. طب لو المطلوب "بعد كام خطوة"؟ ساعتها الـ values مش هتكفي.

مثال محلول 5: Daily Temperatures

الجديد هنا إن الإجابة مسافة مش قيمة، فالـ indices بقت لازمة.

Daily Temperatures

mediumLeetCode 739

عندك درجة الحرارة لكل يوم. لكل يوم، عايز تعرف هتستنى كام يوم لحد ما ييجي يوم أدفى منه. لو مفيش يوم أدفى بعده خالص، الإجابة 0.

Input: temps = [30, 33, 31, 29, 32, 35, 34] Output: [1, 4, 2, 1, 1, 0, 0] (day 1 is 33; the first warmer day is day 5 (35), so it waits 5 - 1 = 4)

نفكّر فيها مع بعض

  1. افهم المطلوب: "أول أكبر على اليمين" بالظبط، بس الإجابة i - j مش temps[i].
  2. Brute force: لكل يوم دوّر قدّام، O(n²). والـ worst case لما الحرارة بتقل كل يوم.
  3. الـ key insight: نفس الـ template، والـ stack فيه indices الأيام المستنية. لو خزّنت درجات الحرارة بس، هتعرف مين مستني بس مش من إمتى.
  4. الفرق الوحيد: الـ default بقى 0 مش -1.
  5. Edge cases: يوم واحد، حرارة ثابتة (المساوي مش أدفى)، كلها بتزيد، وكلها بتقل.
  1. fill(0)، لأن المسألة قالت لو مفيش يوم أدفى الإجابة 0.
  2. indices الأيام المستنية، وحرارتهم من تحت لفوق متناقصة أو متساوية.
  3. < مش <=: آخر index هو length - 1، و temps[length] هتبقى undefined.
  4. > لأن "أدفى" يعني أكبر، واليوم المساوي مش إجابة (شوف [50, 50, 50] في الجدول تحت).
  5. الانتظار i - j مش i - j + 1: من يوم 1 ليوم 5 بتستنى 4 أيام. ده مسافة بين يومين، مش عدد عناصر في range.
  6. اليوم الحالي يستنى يوم أدفى منه.
  7. الأيام اللي فضلت في الـ 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 وارجعلها بعدين.

Largest Rectangle in Histogram

hardLeetCode 84

عندك أعمدة جنب بعض، عرض كل عمود 1 وارتفاعه heights[i]. هات مساحة أكبر مستطيل تقدر ترسمه جوه الأعمدة دي. المستطيل قاعد على الأرض، وارتفاعه ما ينفعش يعدّي أقصر عمود تحته.

Input: heights = [2, 4, 5, 3, 1, 3] Output: 9 (height 3 over bars 1..3: 3 * 3)

نفكّر فيها مع بعض

  1. Brute force: لكل range، المساحة = أقصر عمود × العرض: O(n²)، و n لحد 10⁵.
  2. اقلب السؤال: لكل عمود: "لو هو أقصر عمود في المستطيل، يتمد لحد فين؟". لحد أول أقصر منه يمين، وأول أقصر منه شمال.
  3. الـ key insight: في stack متزايد، لما عمود يعمل pop بسبب i، يبقى i أول أقصر منه يمين، واللي تحته في الـ stack أول أقصر منه شمال.
  4. العرض: الأعمدة اللي بين الحدّين من غيرهم: i - left - 1.
  5. الأعمدة اللي هتفضل في الآخر: عمود وهمي ارتفاعه 0 عند i = n بيعمل pop لكلهم.
  1. indices، والارتفاعات من تحت لفوق متزايدة، لأننا بندوّر على أول أصغر.
  2. best = 0 لأن أقل مساحة ممكنة صفر.
  3. هنا <= مقصودة: اللفة الزيادة عند i = n هي العمود الوهمي. بـ <، الـ [1, 2, 3] هتطلع 0 بدل 4 لأن مفيش ولا pop.
  4. heights[n] = undefined، فبنستخدم 0 بدلها، والـ 0 أقصر من الكل فبيفضّي الـ stack.
  5. العمود الجديد أقصر من اللي فوق، فاللي فوق اتقفل من اليمين. المتساوي بنسيبه، لأن آخر واحد في المتساويين هيحسب العرض كله (و <= بتدّي نفس الإجابة برضه).
  6. top هو أقصر عمود في المستطيل اللي بنحسبه.
  7. left هو اللي تحته، أول أقصر منه شمال. لو الـ stack فضي يبقى الحد -1 مش 0، لأن الحد نفسه مش داخل والعمود 0 داخل.
  8. الأعمدة من left + 1 لـ i - 1، وعددهم (i - 1) - (left + 1) + 1 = i - left - 1.
  9. المساحة = ارتفاع top × العرض.
  10. العمود الحالي يدخل، والـ 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]0best بتبدأ من 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:

Stack overflow الـ call stack حجمه محدود. في Node، 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].

تمرين: فكّر قبل ما تفتح

Next Greater Element II

mediumLeetCode 503

نفس "أول أكبر على اليمين"، بس الـ array دايرية: بعد آخر عنصر بترجع لأول عنصر. والأرقام ممكن تتكرر. لو مفيش أكبر، -1.

[3, 8, 4, 1, 2] → [8, -1, 8, 2, 3] (the 2 at the end goes around: next is 3, which is bigger)
تلميح 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 بتاعها هنا، وبعدين حاول تاني من غير ما تبص.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة Stack يعني: افتكر الحاجات اللي لسه مفتوحة أو مستنية، والأحدث فيهم يتعامل الأول. ولو المستنيين بيدوّروا على "أول أكبر" أو "أول أصغر"، خليهم مترتبين، وده الـ monotonic stack.
السؤالالإجابة
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 من جوه.