ओ (1) वेळ आणि ओ (1) अतिरिक्त जागेमध्ये गेटमिन () ला समर्थन देणारे स्टॅक डिझाइन करा  


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन फॅक्टसेट फ्लिपकार्ट गोल्डमन Sachs ग्रेऑरेंज कुलिझा मायक्रोसॉफ्ट पेटीएम पब्लिसिस सेपिएंट सॅप Snapdeal व्हीएमवेअर
स्टॅक

ओ (1) वेळ आणि ओ (1) अतिरिक्त जागेमध्ये गेटमिन () ला समर्थन देणारे स्टॅक डिझाइन करा. अशा प्रकारे विशेष स्टॅक डेटा स्ट्रक्चरने स्टॅकच्या सर्व ऑपरेशन्सचे समर्थन केले पाहिजे -

  • शून्य पुश ()
  • इंट पॉप ()
  • पूर्ण आहे ()
  • बूल इम्प्टी ()

सतत वेळेत. स्थिर वेळेत अतिरिक्त स्टॅकमध्ये किमान मूल्य आणि ओ (1) अतिरिक्त जागा परत करण्यासाठी अतिरिक्त ऑपरेशन गेटमिन () जोडा.

ओ (1) वेळ आणि ओ (1) अतिरिक्त जागेमध्ये गेटमिन () ला समर्थन देणारे स्टॅक डिझाइन करापिन

उदाहरण  

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. स्टॅक रिक्त आहे का ते तपासा, स्टोअर करा पूर्णांक व्हेरिएबल मिनिट मध्ये, स्टॅक मध्ये रिटर्न आणि पूर्णांक संख्या द्या.
  3. अन्यथा पूर्णांक मिनिटापेक्षा कमी असल्यास 2 * x - मिनिट स्टॅकमध्ये आणि मिनिट x म्हणून अद्यतनित करा.
  4. अन्यथा पूर्णांक पूर्ण दाबा.
  5. फंक्शन पॉप () तयार करा. स्टॅक रिक्त आहे का ते तपासा “स्टॅक रिक्त आहे” आणि परत या.
  6. अन्यथा व्हेरिएबल टी मध्ये स्टॅकच्या शीर्षस्थानी घटक साठवा आणि स्टॅकमधून शीर्ष घटक पॉप / काढा.
  7. टी प्रिंट मिनिटापेक्षा कमी आहे का ते तपासा आणि मिनिट 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) प्रत्येक ऑपरेशनसाठी, कारण सर्व ऑपरेशन्स स्थिर वेळेत केल्या जात आहेत.

हे सुद्धा पहा
स्ट्रिंगमध्ये नेस्टेड पॅरेन्थेसिसची जास्तीत जास्त खोली शोधा

स्पेस कॉम्प्लेक्सिटी

ओ (1) कारण आम्ही घटकांची सहाय्य करणारी जागा वापरत आहोत. इनपुट संचयित करण्यासाठी आवश्यक जागा अल्गोरिदमच्या अवकाश जटिलतेनुसार मोजली जात नाही.