ایک اسٹیک ڈیزائن کریں جو O (1) وقت اور O (1) اضافی جگہ میں getMin () کی تائید کرے


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون حقیقت Flipkart گولڈمین سیکس گرین اورنج کلیزا مائیکروسافٹ پی ٹی ایم ایم پبلسس سیپینٹ SAP Snapdeal VMware
اسٹیک

ایک اسٹیک ڈیزائن کریں جو O (1) وقت اور O (1) اضافی جگہ میں getMin () کی تائید کرے۔ اس طرح خصوصی ڈھیر لگانا ڈیٹا ڈھانچہ کو اسٹیک کے تمام کاموں کی حمایت کرنا چاہئے جیسے۔

  • باطل دھکا ()
  • انٹ پاپ ()
  • بول مکمل ہے ()
  • بول ہےEmpty ()

مستقل وقت میں مستقل وقت میں خصوصی اسٹیک میں کم سے کم قیمت اور O (1) اضافی جگہ واپس کرنے کے لئے ایک اضافی آپریشن getMin () شامل کریں۔

ایک اسٹیک ڈیزائن کریں جو O (1) وقت اور O (1) اضافی جگہ میں getMin () کی تائید کرے

مثال کے طور پر

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

منسٹ اسٹیک کے نفاذ کے لئے ریاضی / مشاہدہ کا طریقہ

اس نقطہ نظر میں ہم کم از کم عنصر کو بطور تازہ کاری کررہے ہیں۔

دھکا () کے فنکشن میں اگر انٹریگر کو دھکا دینا کم سے کم عنصر سے کم ہوتا ہے تو ہم اسٹیک میں اس انٹیگر منفی کم سے کم عنصر سے دو بار ڈال رہے ہیں جو ہمیشہ دیئے گئے انٹیجر سے چھوٹا ہوگا۔

  • دیئے گئے عدد <کم سے کم عنصر جس کا مطلب دیئے گئے اعداد - کم سے کم عنصر <0 ہیں
  • // دونوں اطراف میں دیئے گئے عدد کو شامل کرنا
  • دیئے گئے عدد - کم سے کم عنصر + دیئے گئے اعداد <0 + دیئے گئے اعداد
  • 2 * دیئے گئے عدد - کم سے کم عنصر <دی عددی
  • ہم 2 * دیئے گئے عدد - کم سے کم عنصر <نیا کم سے کم عنصر کا نتیجہ اخذ کرسکتے ہیں

لہذا اس عنصر کو پاپ کرتے ہوئے یہ کم سے کم عنصر سے کم ہوگا لہذا ہم کم سے کم عنصر کو اپ ڈیٹ کریں گے۔

اسی طرح ، پاپ () فنکشن میں ، اگر موجودہ عنصر کم سے کم عنصر سے کم ہو تو ہم اسے اپ ڈیٹ کریں گے۔

الگورتھم

  1. کسی ڈھانچے کو شروع کریں نیا اسٹیک اور ایک فنکشن بنائیں دھکا () اس میں جو ایک پیرامیٹر کے طور پر کسی عدد کو قبول کرتا ہے۔
  2. چیک کریں کہ اسٹیک خالی ہے ، اسٹور کریں عددی متغیر کم سے کم میں ، اسٹیک میں واپس اوپر اور انٹرنر ڈالیں۔
  3. بصورت دیگر اگر انٹیجر 2 * x - منٹ اسٹیک میں کم سے کم XNUMX داخل کریں اور منٹ کو x کے بطور اپ ڈیٹ کریں۔
  4. ورنہ اسٹیک میں عددی کو دبائیں۔
  5. فنکشن پاپ () بنائیں۔ چیک کریں کہ آیا اسٹیک خالی ہے؟ “اسٹیک خالی ہے” اور واپس آجائیں۔
  6. ورنہ متغیر ٹی میں اسٹیک کے اوپری حصے پر عنصر کو اسٹور کریں اور پوپ / ٹاپ عنصر کو اسٹیک سے ہٹا دیں۔
  7. چیک کریں اگر t منٹ منٹ سے کم منٹ ہے اور منٹ کو 2 * منٹ - t کے طور پر اپ ڈیٹ کریں۔
  8. دوسری پرنٹ ٹی.
  9. getMin () فنکشن بنائیں اور چیک کریں کہ آیا اسٹیک خالی پرنٹ ہے "اسٹیک خالی ہے"۔
  10. ورنہ کم از کم عنصر کو لوٹائیں۔

ضابطے

منٹ اسٹیک کیلئے سی ++ پروگرام

#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 کے لئے جاوا پروگرام

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (1) ہر آپریشن کے ل، ، کیونکہ تمام آپریشن مستقل وقت میں کیے جارہے ہیں۔

خلائی پیچیدگی

O (1) کیونکہ ہم متضاد معاون جگہ استعمال کر رہے ہیں۔ ان پٹ کو ذخیرہ کرنے کے لئے درکار جگہ الگورتھم کی جگہ کی پیچیدگی کے حساب سے نہیں ہے۔