அதிகபட்ச அடுக்கு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது ஆப்பிள் Lyft கிழித்து
வடிவமைப்பு ஸ்டேக்

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

இந்த செயல்பாடுகளைச் செய்யக்கூடிய ஒரு சிறப்பு அடுக்கை வடிவமைக்க “மேக்ஸ் ஸ்டேக்” சிக்கல் கூறுகிறது:

  1. மிகுதி (x): ஒரு உறுப்பை அடுக்கில் தள்ளவும்.
  2. மேல் (): அடுக்கின் மேற்புறத்தில் உள்ள உறுப்பை வழங்குகிறது.
  3. பாப் (): மேலே உள்ள அடுக்கிலிருந்து உறுப்பை அகற்றவும்.
  4. peekmax (): அடுக்கின் அதிகபட்ச உறுப்பை வழங்குகிறது.
  5. பாப்மேக்ஸ் (): அடுக்கிலிருந்து அதிகபட்ச உறுப்பை அகற்றி அதைத் திருப்பித் தரவும்.

அடுக்கில் பல அதிகபட்ச கூறுகள் இருந்தால் popmax () மேலே உள்ள ஒரே ஒரு உறுப்பை மட்டும் அகற்றவும்.

கடைசி நான்கு செயல்பாடுகளுக்கு, இது அடுக்கு காலியாக இல்லை என்பது உறுதி, இல்லையெனில் இந்த செயல்பாடுகள் அழைக்கப்படாது.

உதாரணமாக  

push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

விளக்கம்

மேக்ஸ் ஸ்டேக்முள்

அணுகுமுறை  

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

peekmax ()

எங்களிடம் அடுக்கு [5,2,3,6,8] உள்ளது என்று வைத்துக்கொள்வோம், எனவே மற்றொரு அடுக்கை பராமரிப்போம். அதிகபட்ச உறுப்பு என பெயரிடலாம், இது அந்த உறுப்பு வரை அதிகபட்சத்தை சேமிக்கும். எனவே கொடுக்கப்பட்ட அடுக்கிற்கு, எங்கள் அதிகபட்ச அடுக்கு [5,5,5,6,8] ஆக இருக்கும். இந்த வழியில், O (1) நேர சிக்கலில் அதிகபட்ச உறுப்பைக் காணலாம்.

popmax ()

பீக்மேக்ஸ் () ஐப் பயன்படுத்தி அடுக்கில் அதிகபட்ச உறுப்பைக் காணலாம். எனவே அடுக்கிலிருந்து உறுப்புகளை பாப் செய்து அதை இடையக அடுக்கில் தள்ளுவோம். அதிகபட்ச உறுப்பைக் கண்டுபிடிக்கும் வரை இதை மீண்டும் செய்வோம்.

மேலும் காண்க
வரிசைப்படுத்தப்பட்ட வரிசையிலிருந்து நகல்களை அகற்று

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

குறியீடு  

மேக்ஸ் ஸ்டேக்கிற்கான சி ++ குறியீடு

class MaxStack {
    public MaxStack() {
         stack<int> tmpStack, maxStack;
    }
    public void push(int x) {
        int max = maxStack.empty() ? x : maxStack.top();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        int tmp=tmpStack.top();
        tmpStack.pop();
        maxStack.pop();
        return tmp;
    }
    public int top() {
        return tmpStack.top();
    }
    public int peekMax() {
        return maxStack.top();
    }
    public int popMax() {
        int mx = peekMax();
        stack<int> buffer;
        while (tmpStack.top() != mx){
            buffer.push(tmpStack.top());
            tmpStack.pop();
        }
        while (!buffer.empty()){
            tmpStack.push(buffer.top());
            buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

மேக்ஸ் ஸ்டேக்கிற்கான ஜாவா குறியீடு

class MaxStack {
    Stack<Integer> tmpStack;
    Stack<Integer> maxStack;
    public MaxStack() {
        tmpStack = new Stack<Integer>();
        maxStack = new Stack<Integer>();
    }
    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        maxStack.pop();
        return tmpStack.pop();
    }
    public int top() {
        return tmpstack.peek();
    }
    public int peekMax() {
        return maxStack.peek();
    }
    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack<Integer>();
        while(tmpStack.top() != mx){
        	buffer.push(tmpStack.top());
        	tmpStack.pop();
        }
        while (!buffer.isEmpty()){
        	tmpStack.push(buffer.top());
        	buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

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

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

  1. மிகுதி (x): ஓ (1) நாம் ஒரு கட்டத்தில் உறுப்புகளை அடுக்கிற்குள் தள்ளலாம்.
  2. பாப் (): ஓ (1) அடுக்கிலிருந்து ஒரு உறுப்பை ஒரே கட்டத்தில் பாப் செய்யலாம்.
  3. மேல் (): ஓ (1) அடுக்கின் மேல் உறுப்பை ஒரே கட்டத்தில் திருப்பித் தரலாம்.
  4. peekmax (): ஓ (1) ஒரே கட்டத்தில் அடுக்கில் அதிகபட்ச உறுப்பைக் காணலாம்.
  5. பாப்மேக்ஸ் (): O (n) மிக மோசமான நிலையில் அதிகபட்ச உறுப்பு அடுக்கின் அடிப்பகுதியில் இருக்கலாம்.

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

O (n) மிக மோசமான நிலையில் அனைத்து கூறுகளும் ஒரே நேரத்தில் அடுக்கில் உள்ளன.