د منټ سټیک لیټکوډ حل


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon مڼه د بلومبرګ پلازمیینه يو د Microsoft سينه_پوښ
ډيزاين د دلۍ

ستونزه بیان

ډیزاین a ډک چې په دوامداره توګه لږترلږه عنصر د فشار ، پاپ ، سر ، او ترلاسه کولو ملاتړ کوي.

فشار (x) - عنصر ایکس په دلۍ کې فشار کړئ.
پاپ () - د دلۍ پر سر عنصر لرې کوي.
پورته () - پورته عنصر ترلاسه کړئ.
getMin () - په دلۍ کې لږترلږه عنصر ترلاسه کړئ.

یادونه: میتودونه پاپ ، پورته او getMin عملیات به تل په خالي خالي سټیکونو غږول کیږي.

بېلګه

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

وضاحت:

MinStack minStack = نوی MinStack ()؛
minStack.push (-2)؛
minStack.push (0)؛
minStack.push (-3)؛
minStack.getMin ()؛ // بیرته -3
minStack.pop ()؛
minStack.top ()؛ // راستنیدنه 0
minStack.getMin ()؛ // بیرته -2

او کړنلاره

موږ پوهیږو چې سټاکس د معلوماتو جوړښت دی چې په هغې کې موږ کولی شو په اسانۍ سره په پای کې یو عنصر فشار ورکړئ او هم په اسانۍ سره وروستي داخل شوي عنصر ته لاسرسی یا پاپ. دا عملیات په O (1) وخت کې په یوه بسته کې پیښیږي. مګر پدې ستونزه کې موږ باید اضافي فعالیت getMin رامینځته کړو چې باید د دې وړتیا ولرئ چې په ګ inه کې لږترلږه عنصر بیرته راشي او دا هم د O (1) وخت کې.

نو د دې ډیټا جوړښت ډیزاین کولو لپاره موږ به په څرګنده توګه د سټایل اصلي ډیټا جوړښت په توګه وکاروو مګر موږ باید پدې کې یو څه اضافي الګوریتم اضافه کړو ترڅو موږ په دوامداره وخت کې لږترلږه عنصر ترلاسه کولو توان ولرو.

د دې لپاره ، راځئ چې یو مثال وګورو. راځئ فرض کړئ چې موږ باید دا عناصر په ترتیباتو کې دننه کړو:
5 6 4 7 5 3 ، او بیا پوپینګ پیل کړئ.

د منټ سټیک لیټکوډ حل

موږ کولی شو مشاهده کړو کله چې موږ عنصر پاپ کړو کوم چې اوسنی لږترلږه هم وي نو نوی لږترلږه ورته دی لکه د فشار ورکولو دمخه. نو موږ باید تر دې دمه د ټولو تیرو لږترلږه عناصرو پوهه ولرو ترڅو موږ د O (1) وخت کې د اوسني لږترلږه عنصر له لرې کولو وروسته لږترلږه ترلاسه کړو.

د دې لپاره موږ یو بل کڅوړه کارولی شو کوم چې به د اصلي سټاک لږترلږه عنصر (په انځر کې د شین رنګ سره ښودل شوی) وساتي. نو د لږترلږه سټیک لوړ عنصر به اوسني لږترلږه عنصر ته ووایی.

د یو عنصر دننه کولو یا حذف کولو په جریان کې به موږ دقیقه بackه په لاندې ډول تازه کړو:

  • که نوی فشار شوی عنصر د اوسني لږترلږه څخه لږ یا مساوي وي نو بیا موږ دا عنصر په منډ سټیک کې هم فشار کوو ترڅو اوسنی لږترلږه تازه کړئ.
  • که چیرې پاپ شوی عنصر د اوسني لږترلږه سره مساوي وي نو بیا موږ دا عنصر د من له زېرمو څخه هم لرې کوو چې اوسني لږترلږه تازه کړئ.

تطبیق

د Min اسٹیک لیټکوډ حل لپاره C ++ برنامه

#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

د Min اسٹیک لیټکوډ حل لپاره جاوا برنامې

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 اسٹیک لیټکوډ حل لپاره د پیچلو تحلیلونه

د وخت پیچلتیا

O (1): O (1) د ټولو عملیاتو لپاره. لکه څنګه چې موږ پوهیږو ټیک د فشار ، پاپ ، او سر لپاره دوامداره وخت نیسي. د ګیټ مین لپاره موږ یو بل سټایل کارولی دی چې دا فنکشن هم په دوامداره وخت کې کار کولو ته اړوي.

د ځای پیچلتیا 

O (n): په بد حالت کې ټول عملیات فشار دی ، له همدې امله د ځای پیچلتیا O (n) ده.