কম্পিউটার

O(1) সময়ে একটি স্ট্যাকে সর্বাধিক এবং C++ এ O(1) অতিরিক্ত স্থান খুঁজুন


ধরুন আমরা একটি স্ট্যাক তৈরি করতে চাই যা স্ট্যাকের মধ্যে সর্বাধিক উপাদান সংরক্ষণ করতে পারে। এবং আমরা এটি O(1) সময়ে পেতে পারি। সীমাবদ্ধতা হল, এটি O(1) অতিরিক্ত স্থান ব্যবহার করবে।

আমরা একটি ব্যবহারকারী-সংজ্ঞায়িত স্ট্যাক তৈরি করতে পারি, যা সর্বাধিক মান সংরক্ষণ করবে, যখন একটি অপারেশন সঞ্চালিত হয়, যেমন পপ বা পিক, তারপর সর্বোচ্চটি ফেরত দেওয়া হবে। পিক অপারেশনের জন্য, পপ অপারেশনের জন্য সর্বোচ্চ স্ট্যাক টপ এবং সর্বোচ্চ এলিমেন্ট ফেরত দিন, যখন টপ এলিমেন্ট বড় হয়, তখন এটি প্রিন্ট করুন এবং সর্বোচ্চ 2*max – top_element হিসেবে আপডেট করুন। অন্যথায় top_element ফেরত দিন। পুশ অপারেশনের জন্য সর্বাধিক উপাদানটিকে x (ডাটা ঢোকানো হবে), 2*x – সর্বোচ্চ হিসাবে আপডেট করুন।

উদাহরণ

#include <iostream>
#include <stack>
using namespace std;
class CustomStack {
   stack<int> stk;
   int stack_max;
   public:
   void getMax() {
      if (stk.empty())
         cout << "Stack is empty"<<endl;
      else
         cout << "Maximum Element in the stack is: "<< stack_max <<endl;
   }
   void peek() {
      if (stk.empty()) {
         cout << "Stack is empty ";
         return;
      }
      int top = stk.top(); // Top element.
      cout << "Top Most Element is: "<<endl;
      (top > stack_max) ? cout << stack_max : cout << top;
   }
   void pop() {
      if (stk.empty()) {
         cout << "Stack is empty"<<endl;
         return;
      }
      cout << "Top Most Element Removed: ";
      int top = stk.top();
      stk.pop();
      if (top > stack_max) {
         cout << stack_max <<endl;
         stack_max = 2 * stack_max - top;
      } else
         cout << top <<endl;
      }
      void push(int element) {
         if (stk.empty()) {
         stack_max = element;
         stk.push(element);
         cout << "Element Inserted: " << element <<endl;
            return;
      }
      if (element > stack_max) {
         stk.push(2 * element - stack_max);
            stack_max = element;
      } else
         stk.push(element);
      cout << "Element Inserted: " << element <<endl;
   }
};
int main() {
   CustomStack stk;
   stk.push(4);
   stk.push(6);
   stk.getMax();
   stk.push(8);
   stk.push(20);
   stk.getMax();
   stk.pop();
   stk.getMax();
   stk.pop();
   stk.peek();
}

আউটপুট

Element Inserted: 4
Element Inserted: 6
Maximum Element in the stack is: 6
Element Inserted: 8
Element Inserted: 20
Maximum Element in the stack is: 20
Top Most Element Removed: 20
Maximum Element in the stack is: 8
Top Most Element Removed: 8
Top Most Element is:
6

  1. C++ এ একটি ম্যাট্রিক্সে প্রতিটি কলামের সর্বোচ্চ উপাদান খুঁজুন

  2. O(n) সময় এবং O(1) অতিরিক্ত স্থানে সদৃশ খুঁজুন - C++ এ 1 সেট করুন

  3. C++ প্রোগ্রাম সর্বাধিক সাবঅ্যারে যোগফল O(n^2) সময় (অনেক পদ্ধতি) খুঁজে বের করতে

  4. O(n) সময়ে সর্বাধিক পুনরাবৃত্তি সংখ্যা এবং Python-এ O(1) অতিরিক্ত স্থান খুঁজুন