সর্বোচ্চ স্ট্যাক


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় আপেল Lyft উবার
নকশা গাদা

সমস্যা বিবৃতি

"ম্যাক্স স্ট্যাক" সমস্যাটি একটি বিশেষ স্ট্যাক ডিজাইন করতে বলে যা এই ক্রিয়াকলাপগুলি সম্পাদন করতে পারে:

  1. ধাক্কা (এক্স): স্ট্যাকের মধ্যে একটি উপাদান ধাক্কা।
  2. শীর্ষ (): স্ট্যাকের শীর্ষে থাকা উপাদানটি প্রদান করে।
  3. পপ (): শীর্ষে থাকা স্ট্যাক থেকে উপাদানটি সরান।
  4. পিকম্যাক্স (): স্ট্যাকের সর্বাধিক উপাদানটি প্রদান করে।
  5. পপম্যাক্স (): স্তুপ থেকে সর্বাধিক উপাদান সরিয়ে এবং এটি ফিরে।

যদি স্ট্যাকটিতে একাধিক সর্বোচ্চ উপাদান থাকে তবে এর জন্য for পপম্যাক্স () শীর্ষস্থানীয় কেবলমাত্র একটি উপাদান মুছুন।

শেষ চারটি ক্রিয়াকলাপের জন্য, এটি অবশ্যই নিশ্চিত যে স্ট্যাকটি খালি নয় অন্যথায় এই অপারেশনগুলি কল করা হবে না।

উদাহরণ

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]। এইভাবে, আমরা ও (1) সময়ের জটিলতায় সর্বাধিক উপাদানটি খুঁজে পেতে পারি।

পপম্যাক্স ()

পিকম্যাক্স () ব্যবহার করে আমরা স্ট্যাকের মধ্যে সর্বাধিক উপাদান সন্ধান করতে পারি। সুতরাং আমরা স্ট্যাক থেকে উপাদানগুলি পপ করব এবং এটিকে একটি বাফার স্ট্যাকের দিকে ঠেলে দেব। সর্বাধিক উপাদান না পাওয়া পর্যন্ত আমরা এটির পুনরাবৃত্তি করব found

তারপরে আমরা স্ট্যাক থেকে সর্বাধিক উপাদানটি পপ করব। এর পরে আমরা বাফার স্ট্যাকের সমস্ত উপাদানগুলিকে আমাদের মূল স্ট্যাকে স্থানান্তর করব।

কোড

সর্বোচ্চ স্ট্যাকের জন্য সি ++ কোড

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. ধাক্কা (এক্স): ও (1) আমরা একক পদক্ষেপে উপাদানগুলিকে স্ট্যাকের মধ্যে ঠেলাতে পারি।
  2. পপ (): ও (1) আমরা একক পদক্ষেপে স্ট্যাক থেকে কোনও উপাদান পপ করতে পারি।
  3. শীর্ষ (): ও (1) আমরা একক পদক্ষেপে স্ট্যাকের শীর্ষ উপাদানটি ফিরিয়ে দিতে পারি।
  4. পিকম্যাক্স (): ও (1) আমরা একক পদক্ষেপে স্ট্যাকের সর্বোচ্চ উপাদান খুঁজে পেতে পারি can
  5. পপম্যাক্স (): ও (এন) সবচেয়ে খারাপ ক্ষেত্রে সর্বাধিক উপাদানটি স্ট্যাকের নীচে থাকতে পারে।

স্থান জটিলতা

ও (এন) সবচেয়ে খারাপ ক্ষেত্রে সমস্ত উপাদান একই সাথে স্ট্যাকটিতে উপস্থিত রয়েছে।