குறைந்தபட்ச அடுக்கு லீட்கோட் தீர்வு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் ப்ளூம்பெர்க் மூலதன ஒன்று மைக்ரோசாப்ட் ஆரக்கிள்
குறியீட்டு வடிவமைப்பு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions ஸ்டேக்

சிக்கல் அறிக்கை  

வடிவமைப்பு ஒரு ஸ்டாக் இது மிகுதி, பாப், மேல் மற்றும் நிலையான உறுப்பை நிலையான நேரத்தில் மீட்டெடுப்பதை ஆதரிக்கிறது.

மிகுதி (x) - உறுப்பு x ஐ அடுக்கில் தள்ளுங்கள்.
பாப் () - அடுக்கின் மேல் உள்ள உறுப்பை நீக்குகிறது.
மேல் () - மேல் உறுப்பு கிடைக்கும்.
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 ஐ உருவாக்க வேண்டும், இது அடுக்கில் உள்ள குறைந்தபட்ச உறுப்பை மீட்டெடுக்க முடியும், அதுவும் O (1) நேரத்திலும்.

எனவே இந்த தரவு கட்டமைப்பை வடிவமைக்க நாம் வெளிப்படையாக முக்கிய தரவு கட்டமைப்பாக அடுக்கைப் பயன்படுத்துவோம், ஆனால் அதற்கு சில கூடுதல் வழிமுறைகளைச் சேர்க்க வேண்டும், இதனால் நிலையான நேரத்தில் குறைந்தபட்ச உறுப்பைப் பெற முடியும்.

இதற்கு, ஒரு உதாரணத்தைக் காணலாம். இந்த கூறுகளை அடுக்கில் செருக வேண்டும் என்று வைத்துக்கொள்வோம்:
5 6 4 7 5 3, பின்னர் உறுத்துவதைத் தொடங்குங்கள்.

குறைந்தபட்ச அடுக்கு லீட்கோட் தீர்வு

தற்போதைய குறைந்தபட்சமாக இருக்கும் உறுப்பை நாம் பாப் செய்யும் போது, ​​புதிய குறைந்தபட்சம் அதைத் தள்ளுவதற்கு முன்பு இருந்ததைப் போலவே இருப்பதை நாம் அவதானிக்கலாம். ஆகவே, முந்தைய குறைந்தபட்ச உறுப்புகள் அனைத்தையும் நாம் இப்போது வரை கொண்டிருக்க வேண்டும், இதன் மூலம் ஓ (1) நேரத்தில் தற்போதைய குறைந்தபட்ச உறுப்பை அகற்றிய பின் குறைந்தபட்சத்தை மீட்டெடுக்க முடியும்.

மேலும் காண்க
சேர்க்கைகள் லீட்கோட் தீர்வு

இதற்காக நாம் மற்றொரு அடுக்கைப் பயன்படுத்தலாம், இது பிரதான அடுக்கின் குறைந்தபட்ச உறுப்பை (அத்திப்பழத்தில் பச்சை நிறத்துடன் குறிப்பிடப்படுகிறது) மட்டுமே சேமிக்கும். எனவே குறைந்தபட்ச அடுக்கின் மேல் உறுப்பு தற்போதைய குறைந்தபட்ச உறுப்பைச் சொல்லும்.

ஒரு உறுப்பைச் செருகும்போது அல்லது அகற்றும்போது, ​​நிமிட அடுக்கை கீழே புதுப்பிப்போம்:

  • புதிய தள்ளப்பட்ட உறுப்பு தற்போதைய குறைந்தபட்சத்தை விட குறைவாகவோ அல்லது சமமாகவோ இருந்தால், தற்போதைய குறைந்தபட்சத்தை புதுப்பிக்க இந்த உறுப்பை நிமிடம் அடுக்கிலும் தள்ளுகிறோம்.
  • பாப் செய்யப்பட்ட உறுப்பு தற்போதைய குறைந்தபட்சத்திற்கு சமமாக இருந்தால், தற்போதைய குறைந்தபட்சத்தை புதுப்பிக்க இந்த உறுப்பை நிமிடம் அடுக்கிலிருந்து அகற்றுவோம்.

நடைமுறைப்படுத்தல்  

குறைந்தபட்ச அடுக்கு லீட்கோட் தீர்வுக்கான சி ++ நிரல்

#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

குறைந்தபட்ச அடுக்கு லீட்கோட் தீர்வுக்கான ஜாவா திட்டம்

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

குறைந்தபட்ச அடுக்கு லீட்கோட் தீர்வுக்கான சிக்கலான பகுப்பாய்வு  

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

ஓ (1): அனைத்து செயல்பாடுகளுக்கும் ஓ (1). புஷ், பாப் மற்றும் டாப் ஆகியவற்றிற்கு ஸ்டேக் நிலையான நேரம் எடுக்கும் என்பது எங்களுக்குத் தெரியும். GetMin க்கு நாங்கள் மற்றொரு அடுக்கைப் பயன்படுத்தினோம், இது இந்த செயல்பாட்டை நிலையான நேரத்தில் வேலை செய்ய வைக்கிறது.

மேலும் காண்க
பிஎஸ்டியில் கே-வது மிகச்சிறிய உறுப்பைக் கண்டறியவும் (பிஎஸ்டியில் ஆர்டர் புள்ளிவிவரம்)

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

ஓ (ந): மோசமான நிலையில் அனைத்து செயல்பாடுகளும் மிகுதி, எனவே இட சிக்கலானது O (n) ஆகும்.