O (1) အချိန်နှင့် O (1) အပိုနေရာများတွင် getMin () ကိုအထောက်အပံ့ပေးသော stack တစ်ခုကိုဒီဇိုင်းဆွဲပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ အချက်အလက် Flipkart Goldman Sachs GreyOrange Kuliza Microsoft က Paytm Publicis Sapient သည် SAP Snapdeal VMware က
စုပုံထား

O (1) အချိန်နှင့် O (1) အပိုနေရာများတွင် getMin () ကိုအထောက်အပံ့ပေးသော stack တစ်ခုကိုဒီဇိုင်းဆွဲပါ။ ထို့ကြောင့်အထူး စုပုံထား အချက်အလက်ဖွဲ့စည်းပုံသည် stack ၏လုပ်ဆောင်မှုအားလုံးကိုထောက်ပံ့ရမည် -

  • ပျက်ပြယ်တွန်းအား ()
  • အင်ပေါ့ပ် ()
  • bool isFull ()
  • bool isEmpty ()

စဉ်ဆက်မပြတ်အချိန်အတွက်။ စဉ်ဆက်မပြတ်သောအချိန်၌အထူး stack အတွင်းရှိအနည်းဆုံးတန်ဖိုးနှင့် O (1) အပိုနေရာများအတွက်အနိမ့်ဆုံးတန်ဖိုးကိုပြန်သွားရန်အပိုဆောင်းစစ်ဆင်ရေး getMin () ထည့်ပါ။

O (1) အချိန်နှင့် O (1) အပိုနေရာများတွင် getMin () ကိုအထောက်အပံ့ပေးသော stack တစ်ခုကိုဒီဇိုင်းဆွဲပါ

နမူနာ

push(30)
push(20)
push(10)
getMin()
pop()
getMin()
Minimum element : 10
Popped element : 10
Minimum element : 20
push(500)
push(50)
push(5)
getMin()
pop()
getMin()
Minimum element : 5
Popped element : 5
Minimum element : 50

minStack ကိုအကောင်အထည်ဖော်ရန်သင်္ချာ / လေ့လာသူနည်းလမ်း

ဤချဉ်းကပ်မှုတွင်ကျွန်ုပ်တို့သည်နိမ့်ဆုံးသောအစိတ်အပိုင်းကို -

integer တွန်းရန်အနည်းဆုံးသောဒြပ်စင်ထက်နည်းလျှင် push () function တွင်ကျွန်ုပ်တို့သည် integer ၏နှစ်ဆထည့်သွင်းခြင်းအားဖြင့် stack ထဲတွင်အနိမ့်ဆုံးအနိမ့်ဆုံးဖြစ်သည်။

  • ပေးထားတဲ့ integer <minimum element = ဆိုလိုသည်မှာ integer - နိမ့်ဆုံး element <0
  • // နှစ်ဖက်စလုံးတွင်ပေးထားသောကိန်းတစ်ခုထည့်ခြင်း
  • ပေးထားသောကိန်း - နိမ့်ဆုံးဒြပ်စင် + ကိန်းသေ <0 + ပေးထားသောကိန်း
  • 2 * ပေးထားသောကိန်း - နိမ့်ဆုံးဒြပ်စင် <ပေးထားသောကိန်း
  • ပေးထားသောကိန်း - 2 * အနိမ့်ဆုံး element အသစ် <နိမ့်ဆုံး element> ကိုကျွန်ုပ်တို့ကောက်ချက်ချနိုင်သည်

ဒီ element ကိုထုတ်ယူလိုက်ရင်အနည်းဆုံး element ထက်နည်းလိမ့်မယ်။ ဒါကြောင့်ကျွန်တော်တို့အနည်းဆုံး element ကို update လုပ်လိမ့်မယ်။

အလားတူစွာ pop () function တွင်၊ လက်ရှိ element သည်အနည်းဆုံး element ထက်လျော့နည်းပါက၎င်းကိုကျွန်ုပ်တို့ update လုပ်မည်။

algorithm

  1. ဖွဲ့စည်းပုံတစ်ခုကိုအစပြုပါ နယူးယောက် နှင့် function ကိုဖန်တီးပါ တွန်း() တစ် ဦး parameter သည်အဖြစ်တစ်ခုကိန်းလက်ခံသောအထဲတွင်။
  2. stack ဗလာဟုတ်မဟုတ်စစ်ဆေးပါ ကိန်း min ကို variable တစ်ခုထဲမှာထည့်ပြီး return ပြန်ပါ။
  3. ကိန်းတစ်ခုသည်မိနစ်ထက်နည်းလျှင် 2 * x - min ထည့်ပြီး stack တွင် min ကို x အဖြစ်ပြောင်းပါ။
  4. ကျန်တစ်ခုသည်ကိန်းပြည့်ကို stack ဖြင့်တွန်းပါ။
  5. pop () function ကိုဖန်တီးပါ။ stack ဗလာဟုတ်မဟုတ်စစ်ဆေးပါ“ Stack пуста” ကိုပြန်ပြီးပြန်လာပါ။
  6. ကျန်သည် stack ၏ထိပ်ရှိ element ကို variable ကို t နှင့်သိမ်းပြီး top element ကို stack မှသိမ်းပါ။
  7. t ဟာ min print min ထက်နည်းမလားစစ်ဆေးပြီး min ကို 2 * min - t အဖြစ် update လုပ်ပါ။
  8. အခြားပုံနှိပ် t ။
  9. getMin () function ကိုဖန်တီးပြီး stack ဗလာဟုတ်မဟုတ်စစ်ဆေးပါ။ “ Stack пуста” ကိုနှိပ်ပါ။
  10. အခြားအနိမ့်ဆုံး element ကိုပြန်လာပါ။

ကုဒ်

minStack အတွက် C ++ အစီအစဉ်

#include <bits/stdc++.h> 
using namespace std; 
  
struct newStack{ 
    stack<int> s; 
    int min; 
  
    void getMin(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
        }
        else{
            cout<<"Minimum element : "<<min<<"\n"; 
        }    
    } 
  
    void pop(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
            return; 
        } 
  
        cout<<"Popped element : "; 
        int t = s.top(); 
        s.pop(); 
  
        if(t<min){ 
            cout<<min<< "\n"; 
            min = 2*min - t; 
        } 
  
        else{
            cout<<t<< "\n";
        }    
    } 
  
    void push(int x){ 
        if(s.empty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x < min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
           s.push(x);
        }   
    } 
}; 
 
int main(){
    newStack s; 
    
    s.push(30);
    s.push(20);
    s.push(10);
    s.getMin();
    s.pop();
    s.getMin();
  
    return 0; 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

minStack အတွက် Java ပရိုဂရမ်

import java.util.*; 
  
class newStack{ 
    Stack<Integer> s; 
    Integer min; 
  
    newStack(){ 
        s = new Stack<Integer>(); 
    } 
  
    void getMin(){ 
        if(s.isEmpty()) 
            System.out.println("Stack is empty"); 
  
        else{
            System.out.println("Minimum element : " + min);
        }    
    } 
  
    void pop(){ 
        if (s.isEmpty()){ 
            System.out.println("Stack is empty"); 
            return; 
        } 
  
        System.out.print("Popped element : "); 
        Integer t = s.pop(); 
  
        if(t<min){ 
            System.out.println(min); 
            min = 2*min - t; 
        } 
  
        else{
            System.out.println(t);
        }    
    } 
  
    void push(Integer x){ 
        if(s.isEmpty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x<min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
            s.push(x); 
        }    
    } 
}; 
  
public class Main{ 
    public static void main(String[] args){ 
        newStack s = new newStack(); 
        
        s.push(30);
        s.push(20);
        s.push(10);
        s.getMin();
        s.pop();
        s.getMin();
        
    } 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (၁) တစ်ခုချင်းစီကိုစစ်ဆင်ရေးများအတွက်, အားလုံးစစ်ဆင်ရေးစဉ်ဆက်မပြတ်အချိန်၌ပြုလျက်ရှိသည်အဖြစ်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ကျနော်တို့ contant အရန်အာကာသကိုအသုံးပြု။ ကြောင့်ဖြစ်သည်။ input ကိုသိမ်းဆည်းရန်လိုအပ်သောနေရာသည် algorithm ၏ရှုပ်ထွေးမှုဆီသို့ ဦး တည်ခြင်းမဟုတ်ပါ။