Σχεδιάστε μια στοίβα που υποστηρίζει getMin () σε χρόνο O (1) και O (1) επιπλέον χώρο


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα Γεγονότα Flipkart Goldman Sachs GreyOrange Κουλίζα Microsoft Paytm Publicis Sapient SAP Snapdeal VMware
Στοίβα

Σχεδιάστε μια στοίβα που υποστηρίζει getMin () σε χρόνο O (1) και O (1) επιπλέον χώρο. Έτσι το ειδικό σωρός η δομή δεδομένων πρέπει να υποστηρίζει όλες τις λειτουργίες της στοίβας όπως -

  • άκυρη ώθηση ()
  • int pop ()
  • bool isFull ()
  • bool isEmpty ()

σε σταθερό χρόνο. Προσθέστε μια πρόσθετη λειτουργία getMin () για να επιστρέψετε την ελάχιστη τιμή σε ειδική στοίβα σε σταθερό χρόνο και O (1) επιπλέον χώρο.

Σχεδιάστε μια στοίβα που υποστηρίζει getMin () σε χρόνο O (1) και O (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

Μαθηματική / Παρατηρημένη μέθοδος για την εφαρμογή του minStack

Σε αυτήν την προσέγγιση ενημερώνουμε το ελάχιστο στοιχείο ως -

Στη λειτουργία push () εάν ο ακέραιος προς ώθηση είναι μικρότερος από το ελάχιστο στοιχείο εισάγουμε δύο φορές από αυτόν τον ακέραιο μείον το ελάχιστο στοιχείο στη στοίβα που θα είναι πάντα μικρότερος από τον δεδομένο ακέραιο όπως -

  • δεδομένο ακέραιο <ελάχιστο στοιχείο που σημαίνει δεδομένο ακέραιο - ελάχιστο στοιχείο <0
  • // Προσθήκη δεδομένου ακέραιου και στις δύο πλευρές
  • δεδομένο ακέραιο - ελάχιστο στοιχείο + δεδομένο ακέραιο <0 + δεδομένο ακέραιο
  • 2 * δεδομένος ακέραιος - ελάχιστο στοιχείο <δεδομένος ακέραιος
  • Μπορούμε να συμπεράνουμε 2 * δεδομένο ακέραιο - ελάχιστο στοιχείο <νέο ελάχιστο στοιχείο

οπότε κατά την εμφάνιση αυτού του στοιχείου θα είναι μικρότερο από το ελάχιστο στοιχείο, επομένως θα ενημερώσουμε το ελάχιστο στοιχείο.

Ομοίως, στη λειτουργία pop (), εάν το τρέχον στοιχείο είναι μικρότερο από το ελάχιστο στοιχείο, θα το ενημερώσουμε.

Αλγόριθμος

  1. Αρχικοποιήστε μια δομή newStack και δημιουργήστε μια συνάρτηση Σπρώξτε() σε αυτό που δέχεται έναν ακέραιο ως παράμετρο.
  2. Ελέγξτε εάν η στοίβα είναι άδεια, αποθηκεύστε το ακέραιος αριθμός σε μεταβλητή min, εισαγάγετε τον ακέραιο στη στοίβα και επιστρέψτε.
  3. Διαφορετικά, εάν ο ακέραιος αριθμός είναι μικρότερος από min, εισάγετε 2 * x - min στη στοίβα και ενημερώστε το min ως x.
  4. Διαφορετικά, σπρώξτε τον ακέραιο στη στοίβα.
  5. Δημιουργήστε τη συνάρτηση pop (). Ελέγξτε εάν η στοίβα είναι κενή εκτύπωση "Η στοίβα είναι άδεια" και επιστρέψτε.
  6. Διαφορετικά, αποθηκεύστε το στοιχείο στην κορυφή της στοίβας σε μια μεταβλητή t και ανοίξτε / αφαιρέστε το κορυφαίο στοιχείο από τη στοίβα.
  7. Ελέγξτε αν η τιμή t είναι μικρότερη από την ελάχιστη εκτύπωση και ενημερώστε την τιμή ως 2 * min - t.
  8. Εκτός εκτύπωσης t.
  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

Πρόγραμμα Java για το 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Ο (1) για κάθε λειτουργία, καθώς όλες οι εργασίες γίνονται σε σταθερό χρόνο.

Διαστημική πολυπλοκότητα

Ο (1) γιατί χρησιμοποιούμε βοηθητικό χώρο. Ο χώρος που απαιτείται για την αποθήκευση της εισόδου δεν υπολογίζεται στην πολυπλοκότητα του διαστήματος του αλγορίθμου.