نمط المكدس الرتيب
طبّق المكدس الرتيب لحل daily-temperatures وlargest-rectangle-in-histogram وnext-greater-element في O(n)
نمط المكدس الرتيب درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ما المكدس الرتيب؟
المكدس الرتيب هو مكدس يحافظ على خاصية ترتيب ثابتة بين عناصره. يحتوي المكدس الرتيب التصاعدي على عناصر تزداد من القاع إلى القمة، بينما يحتوي المكدس الرتيب التنازلي على عناصر تتناقص من القاع إلى القمة. عندما ينتهك عنصر جديد خاصية الثبات، تُزال العناصر من القمة حتى تُستعاد الخاصية، ثم يُدفَع العنصر الجديد إلى المكدس.
تتيح هذه الآلية البسيطة الإجابة بتعقيد O(n) عن استعلامات «العنصر الأكبر الأقرب» و«العنصر الأصغر الأقرب»، التي كانت ستتطلب بصورة مباشرة حلقات متداخلة بتعقيد O(n²).
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)العنصر الأكبر التالي (LeetCode 496)
لكل عنصر، اعثروا على أول عنصر إلى يمينه يكون أكبر منه بشكل صارم. يمسح الحل بالقوة الغاشمة باتجاه اليمين من كل موضع بتعقيد O(n²). أما نهج المكدس الرتيب فيحافظ على مكدس تنازلي من الفهارس. عند العثور على عنصر أكبر، أزيلوا جميع الفهارس ذات العناصر الأصغر؛ فعنصرها الأكبر التالي هو العنصر الحالي. أما الفهارس المتبقية فلا تملك عنصرًا أكبر تاليًا، لذا تكون الإجابة -1.
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]العنصر الأكبر التالي في مصفوفة دائرية
LeetCode 503 «Next Greater Element II»: المسألة نفسها، لكن تُعامل المصفوفة على أنها دائرية. بعد الوصول إلى النهاية، عودوا إلى البداية وتحققوا من العناصر هناك. تكمن الحيلة في المرور عبر المصفوفة مرتين (من الفهرس 0 إلى 2n-1)، واستخدام i % n للفهرسة داخل المصفوفة الأصلية. ادفعوا إلى المكدس الفهارس الواقعة ضمن النطاق [0, n-1] فقط لتجنب معالجة العناصر مرتين.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]درجات الحرارة اليومية: الحل الكامل
نعيد النظر في LeetCode 739: لكل يوم، كم يومًا نحتاج إلى الانتظار حتى نجد درجة حرارة أعلى؟ يحتفظ المكدس الرتيب بفهرس الأيام التي تكون درجات حرارتها في ترتيب تنازلي. عند العثور على يوم أدفأ i، أزيلوا من المكدس جميع فهارس الأيام الأبرد j، وسجّلوا result[j] = i - j. أما الأيام المتبقية في المكدس فلم تجد يومًا أدفأ، ولذلك تبقى نتيجتها 0.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]العنصر الأصغر السابق
يسأل استعلام «العنصر الأصغر السابق» عن أقرب قيمة أصغر إلى يسار كل عنصر. استخدموا مكدسًا رتيبًا تصاعديًا أثناء المعالجة من اليسار إلى اليمين. قبل دفع الفهرس i إلى المكدس، يكون العنصر الموجود في قمته هو العنصر الأصغر السابق، لأن جميع العناصر الأكبر من nums[i] أزيلت بالفعل أثناء عمليات الإدراج السابقة التي أدت إلى إزالة العناصر الأكبر منها.
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]أكبر مستطيل في المدرج التكراري
LeetCode 84 «Largest Rectangle in Histogram»: استخدموا مكدسًا رتيبًا تصاعديًا من الفهارس. لكل عمود، أزيلوا جميع الأعمدة الأطول من العمود الحالي. لكل عمود h أُزيل من المكدس، يكون حدّه الأيمن هو الفهرس الحالي i، وحدّه الأيسر هو قمة المكدس الجديدة + 1، أو 0 إذا كان المكدس فارغًا. المساحة = h × (right - left). أضيفوا حارسًا بارتفاع 0 لإجبار جميع الأعمدة المتبقية على الإزالة في النهاية.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1المستطيل الأقصى (LeetCode 85)
توسّع LeetCode 85 «Maximal Rectangle» مسألة المدرج التكراري إلى مصفوفة ثنائية الأبعاد من القيم الثنائية. لكل صف، احسبوا ارتفاعات الأعمدة المتراكمة: إذا كان matrix[row][col] == '1'، فالارتفاع هو عدد القيم 1 المتتالية فوق هذه الخلية ومعها. بعد ذلك طبّقوا خوارزمية «أكبر مستطيل في المدرج التكراري» على مصفوفة الارتفاعات لكل صف. الزمن: O(m × n) لمصفوفة أبعادها m×n.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6احتجاز مياه الأمطار: نهج المكدس
LeetCode 42 «Trapping Rain Water» باستخدام مكدس: حافظوا على مكدس تنازلي من الفهارس. عند العثور على عمود أطول، يتشكل منخفض. أزيلوا قاع المنخفض، واحسبوا عرض الماء على أنه (current_index - stack_top - 1)، وارتفاعه على أنه (min(current_bar, new_stack_top_bar) - valley_height). اجمعوا جميع المساهمات. الزمن: O(n)، والذاكرة: O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9التعرّف على مسائل المكدس الرتيب
تدل المؤشرات التالية على أن المكدس الرتيب هو الأداة المناسبة: أن تطلب المسألة العنصر الأكبر أو الأصغر التالي أو السابق، أو أن تعتمد إجابة كل عنصر على عناصر في اتجاه محدد، أو أن يتضمن الحل الساذج بتعقيد O(n²) مسحًا إلى اليسار أو اليمين لكل عنصر. يخزّن المكدس المرشحين الذين قد يمثلون إجابات للعناصر اللاحقة، ويتخلص منهم بمجرد وصول مرشح أفضل.
حدّدوا مسبقًا: هل تحتاجون إلى مكدس تصاعدي (للعنصر الأصغر التالي أو السابق) أم تنازلي (للعنصر الأكبر التالي أو السابق)، ومن أي اتجاه ستتم المعالجة.
تحليل التعقيد التراكمي O(n)
قد تبدو خوارزميات المكدس الرتيب ذات تعقيد O(n log n) أو O(n²) للوهلة الأولى بسبب وجود حلقة while داخل حلقة for. لكن كل عنصر يُدفَع إلى المكدس مرة واحدة كحد أقصى ويُزال منه مرة واحدة كحد أقصى. يساوي العدد الإجمالي لعمليات الدفع n، كما لا يتجاوز العدد الإجمالي لعمليات الإزالة n. لذلك يبلغ إجمالي العمل عبر جميع التكرارات 2n عملية، أي O(n) تراكميًا، وليس O(n²).
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nالخلاصة: اختيار خاصية الثبات في المكدس الرتيب
اختاروا اتجاه المكدس بناءً على الاستعلام. بالنسبة إلى العنصر الأكبر التالي، استخدموا مكدسًا تنازليًا؛ وأزيلوا العنصر عندما يكون العنصر الحالي أكبر. وبالنسبة إلى العنصر الأصغر التالي، استخدموا مكدسًا تصاعديًا؛ وأزيلوا العنصر عندما يكون العنصر الحالي أصغر. وبالنسبة إلى أكبر مستطيل، استخدموا مكدسًا تصاعديًا وأزيلوا العناصر عند ظهور عمود أقصر. وبالنسبة إلى القيمة القصوى في النافذة المنزلقة، استخدموا deque تنازليًا وأزيلوا العناصر من كلا الطرفين.
توضح كتابة خاصية الثبات في تعليق قبل البرمجة المنطق وتسرّع تصحيح الأخطاء.
اختبار سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep من هذا الدرس.
خلاصة الدرس
تعلّمتم في هذا الدرس أن: المكدس الرتيب يحافظ على خاصية ترتيب ثابتة عبر إزالة العناصر التي تنتهكها قبل دفع العنصر الجديد، وأن المكدسات التنازلية تجيب عن استعلامات العنصر الأكبر التالي، بينما تجيب المكدسات التصاعدية عن استعلامات العنصر الأصغر التالي، وأن الزمن الإجمالي هو O(n) تراكميًا لأن كل عنصر يُدفَع ويُزال مرة واحدة كحد أقصى. بعد ذلك سننفّذ الطوابير باستخدام المكدسات والمكدسات باستخدام الطوابير.
الأسئلة الشائعة
هل درس «نمط المكدس الرتيب» مجاني؟
نعم — نص درس «نمط المكدس الرتيب» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «نمط المكدس الرتيب»؟
طبّق المكدس الرتيب لحل daily-temperatures وlargest-rectangle-in-histogram وnext-greater-element في O(n) تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «نمط المكدس الرتيب»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.