O (1) समय र O (1) अतिरिक्त स्थानमा getMin () समर्थन गर्दछ एक स्ट्याक डिजाइन गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन तथ्य फ्लिपकार्ट Goldman सैक्स ग्रेऑरेंज कुलिजा माइक्रोसफ्ट पेटम पब्लिसिस सेपिएन्ट SAP स्नैपडल VMware
थाक

O (1) समय र O (1) अतिरिक्त स्थानमा getMin () समर्थन गर्दछ एक स्ट्याक डिजाइन गर्नुहोस्। यसैले विशेष स्ट्याक डाटा संरचनाले स्ट्याकको सबै अपरेसनहरू समर्थन गर्नुपर्दछ -

  • शून्य धक्का ()
  • इंट पप ()
  • Bool isFull ()
  • Bool isEmpty ()

स्थिर समयमा। थप अपरेशन getMin () थप्नुहोस् विशेष स्ट्याकमा स्थिर समयमा न्यूनतम मान र O (१) अतिरिक्त ठाउँ।

O (1) समय र O (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

MinStack कार्यान्वयनको लागि गणितीय / अवलोकन विधि

यस दृष्टिकोणमा हामी न्यूनतम तत्त्वलाई निम्नको रूपमा अपडेट गर्दैछौं -

पुश () प्रकार्यमा यदि इन्टिजर धकेल्न न्यूनतम तत्त्व भन्दा कम हो भने हामी त्यो इन्टिजर शून्यमा न्यूनतम तत्वको दुई पटक सम्मिलित गर्दछौं जुन सधैं दिइने पूर्णांक भन्दा सानो हुन्छ -

  • दिइएको पूर्णांक <न्यूनतम तत्त्वको अर्थ दिइएको इन्टिजर - न्यूनतम तत्व <०
  • // दुबै पक्षमा दिइएको पूर्णांक थप्दै
  • दिइएको पूर्णांक - न्यूनतम तत्त्व + दिइएको पूर्णांक <० + दिईएको पूर्णांक
  • २ * दिइएको पूर्णांक - न्यूनतम तत्त्व <दिइएका पूर्णांक
  • हामी 2 * दिइएको पूर्णांक - न्यूनतम तत्व <नयाँ न्यूनतम तत्वको निष्कर्ष निकाल्न सक्छौं

त्यसैले यो तत्व बाहिर पप्पिंग गर्दा यो न्यूनतम तत्व भन्दा कम हुनेछ त्यसैले हामी न्यूनतम तत्व अपडेट गर्नेछौं।

त्यस्तै पप () प्रकार्यमा यदि हालको तत्व न्यूनतम तत्त्व भन्दा कम छ भने हामी त्यसलाई अपडेट गर्नेछौं।

अल्गोरिदम

  1. संरचना सुरु गर्नुहोस् newStack र प्रकार्य सिर्जना गर्नुहोस् धक्का () यो मा एक मापदण्ड को रूप मा एक पूर्णांक स्वीकार गर्दछ।
  2. स्ट्याक खाली छ कि छैन जाँच गर्नुहोस्, भण्डार गर्नुहोस् पूर्णांक भ्यारीएबल मिनेटमा, स्ट्याकमा र इन्टर्जर घुसाउनुहोस्।
  3. अन्यथा यदि पूर्णांक न्यूनतम सम्मिलित 2 * x - मिनेट स्ट्याकमा मिनेट भन्दा कम छ र x को रूपमा मिनेट अपडेट गर्नुहोस्।
  4. अन्यथा स्ट्याक मा पूर्णांक धक्का।
  5. प्रकार्य पप () सिर्जना गर्नुहोस्। स्ट्याक खाली छ कि छैन जाँच गर्नुहोस् "स्ट्याक खाली छ" र फर्कनुहोस्।
  6. अन्यथा एलिमेन्ट स्ट्याकको शीर्षमा चर भ्यारीएबल टी मा र पप / शीर्ष एलिमेन्ट स्ट्याकबाट हटाउनुहोस्।
  7. T t न्यूनतम प्रिन्ट मिनेट भन्दा कम छ कि छैन जाँच गर्नुहोस् र मिनेट २ * मिनेट - t को रूपमा अपडेट गर्नुहोस्।
  8. अन्य प्रिन्ट टी।
  9. प्रकार्य getMin () सिर्जना गर्नुहोस् र यदि स्ट्याक खाली छ भने जाँच गर्नुहोस् "स्ट्याक खाली छ"।
  10. नत्र न्यूनतम तत्व फिर्ता गर्नुहोस्।

कोड

C ++ कार्यक्रम minStack का लागि

#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

MinStack का लागि जाभा कार्यक्रम

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

जटिलता विश्लेषण

समय जटिलता

O (१) प्रत्येक अपरेशनको लागि, किनकि सबै अपरेशन्स स्थिर समयमा गरिन्छ।

ठाउँ जटिलता

O (१) किनकि हामी कन्टेन्ट सहायक स्थान प्रयोग गर्दैछौं। इनपुट भण्डारण गर्न आवश्यक खाली ठाउँ एल्गोरिथ्मको अन्तरिक्ष जटिलतामा गणना हुँदैन।