حل Min Stack Leetcode  


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون أجهزة آبل بلومبرغ عاصمة واحدة Microsoft أوراكل
خوارزميات الترميز تصميم المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions كومة

المشكلة بيان  

التصميم أ كومة يدعم خاصية push و pop و top و استرداد الحد الأدنى من العناصر في وقت ثابت.

push (x) - ادفع العنصر x إلى المكدس.
pop () - يزيل العنصر الموجود أعلى المكدس.
top () - احصل على العنصر العلوي.
getMin () - استرداد الحد الأدنى للعنصر في المكدس.

ملاحظة: سيتم استدعاء عمليات pop و top و getMin دائمًا على مجموعات غير فارغة.

مثال

push(-2);
push(0);
push(-3);
getMin();
pop();
top();
getMin();
-3
0
-2

التفسير:

MinStack minStack = new MinStack () ؛
minStack.push (-2) ؛
minStack.push (0) ؛
minStack.push (-3) ؛
minStack.getMin () ، // العودة -3
minStack.pop () ،
minStack.top () ، // إرجاع 0
minStack.getMin () ، // العودة -2

الرسالة  

نحن نعلم أن المكدس عبارة عن بنية بيانات يمكننا من خلالها بسهولة دفع عنصر في النهاية وأيضًا الوصول بسهولة إلى آخر عنصر مدرج أو إدخاله. تحدث هذه العمليات في وقت O (1) في مكدس. ولكن في هذه المشكلة ، يتعين علينا إنشاء وظيفة إضافية getMin والتي يجب أن تكون قادرة على استعادة الحد الأدنى للعنصر في المكدس وذلك أيضًا في وقت O (1).

لذلك لتصميم بنية البيانات هذه ، من الواضح أننا سنستخدم المكدس كهيكل بيانات رئيسي ولكن يتعين علينا إضافة بعض الخوارزمية الإضافية إليها حتى نتمكن من الحصول على الحد الأدنى من العناصر في وقت ثابت.

لهذا ، دعونا نرى مثالا. لنفترض أنه يتعين علينا إدراج هذه العناصر بالترتيب:
5 6 4 7 5 3 ، ثم ابدأ الفرقعة.

انظر أيضا
تركيبات Leetcode Solution

حل Min Stack Leetcodeدبوس

يمكننا أن نلاحظ أنه عندما نظهر العنصر الذي يمثل أيضًا الحد الأدنى الحالي ، فإن الحد الأدنى الجديد هو نفسه كما كان قبل دفعه. لذلك يجب أن يكون لدينا معرفة بجميع العناصر الدنيا السابقة حتى الآن حتى نتمكن من استرداد الحد الأدنى بعد إزالة الحد الأدنى الحالي للعنصر في وقت O (1).

لهذا يمكننا استخدام مكدس آخر سيخزن فقط الحد الأدنى من العناصر (ممثلة باللون الأخضر في الشكل) للمكدس الرئيسي. لذا فإن العنصر العلوي من الحد الأدنى للمكدس سيخبرنا بالحد الأدنى الحالي للعنصر.

أثناء إدراج عنصر أو إزالته ، سنقوم بتحديث min stack على النحو التالي:

  • إذا كان العنصر المدفوع الجديد أقل من أو يساوي الحد الأدنى الحالي ، فإننا ندفع هذا العنصر إلى min stack أيضًا لتحديث الحد الأدنى الحالي.
  • إذا كان العنصر المنبثق يساوي الحد الأدنى الحالي ، فسنزيل هذا العنصر من المكدس min أيضًا لتحديث الحد الأدنى الحالي.

تطبيق  

برنامج C ++ لمحلول Min Stack Leetcode

#include <bits/stdc++.h>
using namespace std;

class MinStack {
public:
    stack<int> st,mn;
    
    void push(int x) 
    {
        if(st.empty() || x<=mn.top())
            mn.push(x);
        st.push(x);
    }
    
    void pop() 
    {
        if(st.top()==mn.top()) 
            mn.pop();
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return mn.top();
    }
};

int main() 
{
    MinStack* minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    int param1 = minStack->getMin(); 
    minStack->pop();
    int param2 = minStack->top();   
    int param3 = minStack->getMin(); 
    
    cout<<param1<<endl;
    cout<<param2<<endl;
    cout<<param3<<endl;
    
    return 0; 
}
-3
0
-2

برنامج Java لحلول Min Stack Leetcode

import java.util.*;
class MinStack {

    Stack<Integer> st=new Stack<>();
    Stack<Integer> mn=new Stack<>();
   
    public void push(int x) 
    {
        if(st.empty() || x<=mn.peek())
            mn.push(x);
        st.push(x);
    }
    
    public void pop() 
    {
        if(st.peek().equals(mn.peek())) 
            mn.pop();
        st.pop();
    }
    
    public int top() 
    {
         return st.peek();
    }
    
    public int getMin() 
    {
        return mn.peek();
    }
}

class Rextester{

  public static void main(String args[])
    {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int param1 = minStack.getMin(); 
        minStack.pop();
        int param2 = minStack.top();   
        int param3 = minStack.getMin(); 
        
    System.out.println(param1);
        System.out.println(param2);
        System.out.println(param3);
    }
}
-3
0
-2

تحليل التعقيد لمحلول Min Stack Leetcode  

تعقيد الوقت

يا (1): O (1) لجميع العمليات. كما نعلم ، يستغرق المكدس وقتًا ثابتًا للدفع والبوب ​​والجزء العلوي. بالنسبة إلى getMin ، استخدمنا مكدسًا آخر يجعل هذه الوظيفة تعمل أيضًا في وقت ثابت.

انظر أيضا
ابحث عن أصغر عنصر k-th في BST (إحصائيات الطلب في BST)

تعقيد الفضاء 

على) : في أسوأ الحالات ، تكون كل العمليات مدفوعة ، وبالتالي يكون تعقيد الفضاء هو O (n).

1