O (1) நேரத்திலும், O (1) கூடுதல் இடத்திலும் getMin () ஐ ஆதரிக்கும் ஒரு அடுக்கை வடிவமைக்கவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் உண்மை , Flipkart கோல்ட்மேன் சாக்ஸ் கிரே ஆரஞ்சு குலிசா மைக்ரோசாப்ட் Paytm பப்ளிஸ் சப்பியண்ட் எஸ்ஏபி Snapdeal , VMware
ஸ்டேக்

O (1) நேரத்திலும், O (1) கூடுதல் இடத்திலும் getMin () ஐ ஆதரிக்கும் ஒரு அடுக்கை வடிவமைக்கவும். இவ்வாறு சிறப்பு ஸ்டாக் தரவு அமைப்பு போன்ற அடுக்கின் அனைத்து செயல்பாடுகளையும் ஆதரிக்க வேண்டும் -

  • வெற்றிட புஷ் ()
  • int பாப் ()
  • bool isFull ()
  • bool isEmpty ()

நிலையான நேரத்தில். சிறப்பு ஸ்டேக்கில் குறைந்தபட்ச மதிப்பை நிலையான நேரத்திலும், ஓ (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 - நிமிடம் அடுக்கில் செருகவும், நிமிடத்தை 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (1) ஒவ்வொரு செயல்பாட்டிற்கும், எல்லா செயல்பாடுகளும் நிலையான நேரத்தில் செய்யப்படுகின்றன.

விண்வெளி சிக்கலானது

ஓ (1) ஏனென்றால் நாங்கள் துணை துணை இடத்தைப் பயன்படுத்துகிறோம். உள்ளீட்டை சேமிக்க தேவையான இடம் வழிமுறையின் இட சிக்கலை நோக்கி கணக்கிடாது.