గరిష్ట స్టాక్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది ఆపిల్ లిఫ్ట్ ఉబెర్
రూపకల్పన స్టాక్

సమస్యల నివేదిక

ఈ కార్యకలాపాలను నిర్వహించగల ప్రత్యేక స్టాక్‌ను రూపొందించడానికి “మాక్స్ స్టాక్” సమస్య పేర్కొంది:

  1. పుష్ (x): ఒక మూలకాన్ని స్టాక్‌లోకి నెట్టండి.
  2. టాప్ (): స్టాక్ ఎగువన ఉన్న మూలకాన్ని అందిస్తుంది.
  3. పాప్(): ఎగువన ఉన్న స్టాక్ నుండి మూలకాన్ని తొలగించండి.
  4. పీక్మాక్స్ (): స్టాక్ యొక్క గరిష్ట మూలకాన్ని అందిస్తుంది.
  5. పాప్‌మాక్స్ (): స్టాక్ నుండి గరిష్ట మూలకాన్ని తీసివేసి తిరిగి ఇవ్వండి.

స్టాక్ బహుళ గరిష్ట అంశాలను కలిగి ఉంటే పాప్‌మాక్స్ () అగ్రస్థానంలో ఉన్న ఒక మూలకాన్ని మాత్రమే తొలగించండి.

చివరి నాలుగు ఆపరేషన్ల కోసం, స్టాక్ ఖాళీగా లేదని ఖచ్చితంగా చెప్పవచ్చు, లేకపోతే ఈ ఆపరేషన్లు పిలువబడవు.

ఉదాహరణ

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

వివరణ

మాక్స్ స్టాక్

అప్రోచ్

విధానం చాలా సులభం. ఇక్కడ మేము గరిష్ట స్టాక్‌ను నిర్వహిస్తాము, అది గరిష్ట మూలకాన్ని ట్రాక్ చేస్తుంది స్టాక్ ఇప్పటివరకు. మూడు ఆపరేషన్లను ప్రారంభించడం సాధారణ స్టాక్ ద్వారా మద్దతిస్తుంది కాబట్టి మేము చివరి రెండు ఆపరేషన్ల కోసం ప్రోగ్రామ్ చేయాలి.

పీక్మాక్స్ ()

మనకు స్టాక్ [5,2,3,6,8] ఉందని అనుకుందాం, కాబట్టి మనం మరొక స్టాక్‌ను నిర్వహిస్తాము. ఆ మూలకం వరకు గరిష్టంగా నిల్వ చేసే గరిష్ట స్టాక్‌గా పేరు పెట్టండి. కాబట్టి ఇచ్చిన స్టాక్ కోసం, మా గరిష్ట స్టాక్ [5,5,5,6,8] అవుతుంది. ఈ విధంగా, మేము O (1) సమయ సంక్లిష్టతలో గరిష్ట మూలకాన్ని కనుగొనవచ్చు.

పాప్‌మాక్స్ ()

పీక్‌మాక్స్ () ను ఉపయోగించి మనం స్టాక్‌లోని గరిష్ట మూలకాన్ని సులభంగా కనుగొనవచ్చు. కాబట్టి మేము స్టాక్ నుండి ఎలిమెంట్లను పాప్ చేసి బఫర్ స్టాక్ లోకి నెట్టివేస్తాము. మేము గరిష్ట మూలకాన్ని కనుగొనే వరకు దీన్ని పునరావృతం చేస్తాము.

అప్పుడు మేము స్టాక్ నుండి గరిష్ట మూలకాన్ని పాప్ చేస్తాము. ఆ తరువాత మేము బఫర్ స్టాక్‌లోని అన్ని అంశాలను మా అసలు స్టాక్‌కు బదిలీ చేస్తాము.

కోడ్

మాక్స్ స్టాక్ కోసం సి ++ కోడ్

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): O (1) మేము ఒకే దశలో మూలకాలను స్టాక్‌లోకి నెట్టవచ్చు.
  2. పాప్(): O (1) మేము స్టాక్ నుండి ఒక మూలకాన్ని ఒకే దశలో పాప్ చేయవచ్చు.
  3. టాప్ (): O (1) మేము స్టాక్ యొక్క పై మూలకాన్ని ఒకే దశలో తిరిగి ఇవ్వవచ్చు.
  4. పీక్మాక్స్ (): O (1) ఒకే దశలో స్టాక్‌లో గరిష్ట మూలకాన్ని కనుగొనవచ్చు.
  5. పాప్‌మాక్స్ (): O (n) చెత్త సందర్భంలో గరిష్ట మూలకం స్టాక్ దిగువన ఉండవచ్చు.

స్థల సంక్లిష్టత

O (n) చెత్త సందర్భంలో అన్ని అంశాలు ఒకే సమయంలో స్టాక్‌లో ఉంటాయి.