O (1) সময় এবং ও (1) অতিরিক্ত স্থানের মধ্যে getMin () সমর্থন করে এমন একটি স্ট্যাক ডিজাইন করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক ফ্যাক্সেট Flipkart গোল্ডম্যান শ্যাস গ্রেআরেঞ্জ কুলিজা মাইক্রোসফট Paytm পাবলিকিস সেপিয়েন্ট এসএপি Snapdeal অথবা VMware
গাদা

ও (1) সময় এবং ও (1) অতিরিক্ত স্থানের মধ্যে getMin () সমর্থন করে এমন একটি স্ট্যাক ডিজাইন করুন। এইভাবে বিশেষ গাদা ডেটা স্ট্রাকচার অবশ্যই স্ট্যাকের সমস্ত ক্রিয়াকলাপ সমর্থন করে -

  • অকার্যকর ধাক্কা ()
  • ইন পপ ()
  • ফুল পুরো ()
  • বুল ইম্পটি ()

ধ্রুব সময়ে। স্থির সময়ে বিশেষ স্ট্যাকের সর্বনিম্ন মান এবং O (1) অতিরিক্ত স্থানটিতে ফেরত পেতে একটি অতিরিক্ত ক্রিয়াকলাপ getMin () যুক্ত করুন।

O (1) সময় এবং ও (1) অতিরিক্ত স্থানের মধ্যে getMin () সমর্থন করে এমন একটি স্ট্যাক ডিজাইন করুন

উদাহরণ

push(30)
push(20)
push(10)
getMin()
pop()
getMin()
Minimum element : 10
Popped element : 10
Minimum element : 20
push(500)
push(50)
push(5)
getMin()
pop()
getMin()
Minimum element : 5
Popped element : 5
Minimum element : 50

মিনিস্ট্যাক বাস্তবায়নের জন্য গাণিতিক / পর্যবেক্ষণ পদ্ধতি

এই পদ্ধতির মধ্যে আমরা ন্যূনতম উপাদানটি আপডেট করছি -

পুশ () ফাংশনে যদি ধাক্কা দেওয়ার জন্য পূর্ণসংখ্যার ন্যূনতম উপাদানটির চেয়ে কম হয় আমরা সেই পূর্ণসংখ্যার বিয়োগের ন্যূনতম উপাদানটির দ্বিগুণ স্তুপে সন্নিবেশ করাই যা সর্বদা হিসাবে প্রদত্ত পূর্ণসংখ্যার চেয়ে ছোট হবে -

  • প্রদত্ত পূর্ণসংখ্যা <ন্যূনতম উপাদান যার অর্থ প্রদত্ত পূর্ণসংখ্যা - ন্যূনতম উপাদান <0
  • // উভয় পক্ষের প্রদত্ত পূর্ণসংখ্যা যোগ করা
  • প্রদত্ত পূর্ণসংখ্যা - সর্বনিম্ন উপাদান + প্রদত্ত পূর্ণসংখ্য <0 + প্রদত্ত পূর্ণসংখ্যা
  • 2 * প্রদত্ত পূর্ণসংখ্যা - সর্বনিম্ন উপাদান <প্রদত্ত পূর্ণসংখ্যা
  • আমরা 2 * প্রদত্ত পূর্ণসংখ্যা - ন্যূনতম উপাদান <নতুন ন্যূনতম উপাদানকে উপসংহার করতে পারি

সুতরাং এই উপাদানটি পপ করার সময় এটি ন্যূনতম উপাদানের চেয়ে কম হবে সুতরাং আমরা সর্বনিম্ন উপাদানটি আপডেট করব।

একইভাবে, পপ () ফাংশনে, যদি বর্তমান উপাদানটি ন্যূনতম উপাদানের চেয়ে কম হয় তবে আমরা এটি আপডেট করব।

অ্যালগরিদম

  1. একটি কাঠামো সূচনা newStack এবং একটি ফাংশন তৈরি করুন ধাক্কা () এটিতে এটি একটি পরামিতি হিসাবে কোনও পূর্ণসংখ্যা গ্রহণ করে।
  2. স্ট্যাকটি খালি আছে কিনা তা পরীক্ষা করুন store পূর্ণসংখ্যা একটি চলক মিনিটে, স্ট্যাক এবং পূর্বে পূর্ণসংখ্যা প্রবেশ করান।
  3. অন্যথায় যদি পূর্ণসংখ্যার পরিমাণ 2 মিনিট কম থাকে তবে x - মিনিট স্ট্যাক এবং মিনিটকে x হিসাবে আপডেট করুন।
  4. অন্যথায় স্ট্যাকের মধ্যে পূর্ণসংখ্যার ধাক্কা।
  5. ফাংশন পপ তৈরি করুন ()। স্ট্যাকটি খালি প্রিন্ট কিনা তা পরীক্ষা করে দেখুন "স্ট্যাকটি খালি আছে" এবং ফিরে আসুন।
  6. অন্যটি একটি ভেরিয়েবল টিতে স্ট্যাকের শীর্ষে উপাদানটি সংরক্ষণ করুন এবং স্ট্যাক থেকে শীর্ষ উপাদানটিকে পপ করুন / সরিয়ে দিন।
  7. T টি প্রিন্ট মিনিটের চেয়ে কম কিনা তা পরীক্ষা করুন এবং মিনিট 2 * মিনিট - টি হিসাবে আপডেট করুন।
  8. অন্য প্রিন্ট টি।
  9. GetMin () ফাংশনটি তৈরি করুন এবং স্ট্যাকটি খালি প্রিন্ট কিনা তা পরীক্ষা করুন "স্ট্যাকটি খালি আছে"।
  10. অন্যথায় ন্যূনতম উপাদানটি ফেরত দিন।

কোড

মিনিস্ট্যাকের জন্য সি ++ প্রোগ্রাম

#include <bits/stdc++.h> 
using namespace std; 
  
struct newStack{ 
    stack<int> s; 
    int min; 
  
    void getMin(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
        }
        else{
            cout<<"Minimum element : "<<min<<"\n"; 
        }    
    } 
  
    void pop(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
            return; 
        } 
  
        cout<<"Popped element : "; 
        int t = s.top(); 
        s.pop(); 
  
        if(t<min){ 
            cout<<min<< "\n"; 
            min = 2*min - t; 
        } 
  
        else{
            cout<<t<< "\n";
        }    
    } 
  
    void push(int x){ 
        if(s.empty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x < min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
           s.push(x);
        }   
    } 
}; 
 
int main(){
    newStack s; 
    
    s.push(30);
    s.push(20);
    s.push(10);
    s.getMin();
    s.pop();
    s.getMin();
  
    return 0; 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

মিনিস্ট্যাকের জন্য জাভা প্রোগ্রাম

import java.util.*; 
  
class newStack{ 
    Stack<Integer> s; 
    Integer min; 
  
    newStack(){ 
        s = new Stack<Integer>(); 
    } 
  
    void getMin(){ 
        if(s.isEmpty()) 
            System.out.println("Stack is empty"); 
  
        else{
            System.out.println("Minimum element : " + min);
        }    
    } 
  
    void pop(){ 
        if (s.isEmpty()){ 
            System.out.println("Stack is empty"); 
            return; 
        } 
  
        System.out.print("Popped element : "); 
        Integer t = s.pop(); 
  
        if(t<min){ 
            System.out.println(min); 
            min = 2*min - t; 
        } 
  
        else{
            System.out.println(t);
        }    
    } 
  
    void push(Integer x){ 
        if(s.isEmpty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x<min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
            s.push(x); 
        }    
    } 
}; 
  
public class Main{ 
    public static void main(String[] args){ 
        newStack s = new newStack(); 
        
        s.push(30);
        s.push(20);
        s.push(10);
        s.getMin();
        s.pop();
        s.getMin();
        
    } 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (1) প্রতিটি অপারেশনের জন্য, যেমন সমস্ত অপারেশন স্থির সময়ে করা হচ্ছে।

স্পেস জটিলতা ity

ও (1) কারণ আমরা কনটেন্ট সহকারী স্থান ব্যবহার করছি। ইনপুট সংরক্ষণের জন্য প্রয়োজনীয় স্থানটি অ্যালগরিদমের স্পেস জটিলতার দিকে গণনা করা হয় না।