Παρακολούθηση του τρέχοντος μέγιστου στοιχείου σε μια στοίβα  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Γεγονότα Φουρκίτες Infosys
Στοίβα

Δήλωση προβλήματος  

Το "Tracking current Maximum Element in a Stack" δηλώνει ότι σας δίνεται ένα σωρός δομή δεδομένων. Δημιουργήστε μια συνάρτηση για να παρακολουθείτε τη μέγιστη τιμή στη στοίβα μέχρι το τρέχον ευρετήριο.

Παρακολούθηση του τρέχοντος μέγιστου στοιχείου σε μια στοίβαΚαρφώστε

Παράδειγμα  

4 19 7 14 20
4 19 19 19 20

Επεξήγηση: Οι μέγιστες τιμές έως ότου εκτυπωθούν οι τρέχοντες δείκτες και εμφανίζονται στην παραπάνω εικόνα. Καθώς συναντάμε έναν αριθμό που είναι μεγαλύτερος από το τρέχον μέγιστο. Η τιμή των τρεχουσών μέγιστων αλλαγών.

40 19 7 14 20 5
40 40 40 40 40 40

Αφελή μέθοδος  

Αλγόριθμος

1. Initialize a stack data structure of integer type.
2. Create an integer variable max and store the element at the top of the stack in it.
3. Whenever we need to find the maximum element, we create a temporary stack to store the elements of main stack.
4. Remove each element from mainStack and store in tmpStack while maintaining the maximum.
4. Print the max.

Σε αφελής προσέγγιση, διατηρούμε μια επιπλέον προσωρινή στοίβα που χρησιμοποιείται για να βρούμε το μέγιστο. Κάθε φορά όποτε χρειαζόμαστε το μέγιστο, διασχίζουμε όλα τα στοιχεία του mainStack. Έτσι, για να διασχίσουμε τα στοιχεία, πρέπει να τα βγάλουμε έξω από την κύρια στοίβα και να τα σπρώξουμε στην προσωρινή στοίβα. Έτσι, αφού διασχίσουμε όλα τα στοιχεία, μπορούμε να τα ωθήσουμε πίσω στην κύρια στοίβα. Έτσι, όποτε χρειαζόμαστε στο μέγιστο μέχρι τώρα, η λειτουργία κοστίζει μια γραμμική πολυπλοκότητα χρόνου του O (N). Έτσι, αν βρούμε το μέγιστο μέχρι κάθε στοιχείο, η συνολική πολυπλοκότητα του χρόνου θα είναι O (N ^ 2).

Βλέπε επίσης
Ταξινόμηση Array κατά Parity II Λύση κωδικού πρόσβασης

Κώδικας

Πρόγραμμα C ++ για παρακολούθηση τρέχοντος μέγιστου στοιχείου σε μια στοίβα

#include <bits/stdc++.h>
using namespace std;

class StackWithMax{
    stack<int> mainStack;

public:
    void push(int x){
        mainStack.push(x);
    }

    int getMax(){
        stack<int> tmpStack;
        int mx = INT_MIN;
        while(!mainStack.empty()){
            tmpStack.push(mainStack.top());
            mainStack.pop();
            mx = max(tmpStack.top(), mx);
        }
        while(!tmpStack.empty()){
            mainStack.push(tmpStack.top());
            tmpStack.pop();
        }
        return mx;
    }

    int pop(){
        mainStack.pop();
    }
};

int main(){
    StackWithMax s;

    s.push(20);
    s.push(14);
    s.push(7);
    s.push(19);
    s.push(4);
    cout<<s.getMax();

    return 0;
}
20

Πρόγραμμα Java για παρακολούθηση τρέχοντος μέγιστου στοιχείου σε μια στοίβα

import java.util.*; 

class TrackMax{ 
  
    static class StackWithMax{  
        static Stack<Integer> mainStack = new Stack<Integer> ();  
        
        static void push(int x){  
                mainStack.push(x);
        }  
          
        static void getMax(){  
            int max = mainStack.peek();
            while(!mainStack.isEmpty()){
                
                if(max<mainStack.peek()){
                    max = mainStack.peek();
                }
                
                System.out.print(max+" ");
                pop();
            } 
        }  
      
        static void pop(){  
            mainStack.pop();  
        }  
    
    };
      
    public static void main(String[] args){  
        StackWithMax s = new StackWithMax();
        
        s.push(20);  
        s.push(14);  
        s.push(7);  
        s.push(19);  
        s.push(4);  
        s.getMax(); 
    } 
}
20

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

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

ΕΠΙ), γιατί διασχίζουμε όλα τα στοιχεία μέσα στη στοίβα ανά λειτουργία getmax ().

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

ΕΠΙ), γιατί χρησιμοποιούμε μια προσωρινή στοίβα για να αποθηκεύσουμε τα στοιχεία της κύριας στοίβας.

Αποτελεσματική μέθοδος  

Αλγόριθμος

1. Initialize a stack data structure of integer type.
2. Create a class and create two stacks main and temporary of integer type in it.
3. After that, create the function push which accepts an integer variable as it's a parameter. Push/insert the integer variable in the main stack.
4. Check if the size of the main stack is equal to 1, push/insert the integer variable in the temporary stack, and return.
5. If the integer variable is greater than the element at the top of the temporary stack, push/insert the integer variable in the temporary stack.
6. Else push/insert the element at the top of the temporary stack in the temporary stack itself.
7. Similarly, create the function to get the maximum element and return the element at the top of the temporary stack.
8. Also, create the function pop. Pop / remove the element at the top of the temporary stack and the main stack.

Κώδικας

Πρόγραμμα C ++ για παρακολούθηση τρέχοντος μέγιστου στοιχείου σε μια στοίβα

#include <bits/stdc++.h> 
using namespace std; 
  
class StackWithMax{ 

    stack<int> mainStack; 
  
    stack<int> trackStack; 
  
public: 
    void push(int x){ 
        mainStack.push(x); 
        
        if(mainStack.size() == 1){ 
            trackStack.push(x); 
            return; 
        } 
  
        if(x > trackStack.top()){ 
            trackStack.push(x); 
        }
        
        else{
            trackStack.push(trackStack.top()); 
        }
    } 
  
    int getMax(){ 
        return trackStack.top(); 
    } 
  
    int pop(){ 
        mainStack.pop(); 
        trackStack.pop(); 
    } 
}; 
  
int main(){ 
    StackWithMax s; 
    
    s.push(4); 
    cout<<s.getMax()<<" ";
    s.push(19);
    cout<<s.getMax()<<" ";
    s.push(7); 
    cout<<s.getMax()<<" ";
    s.push(14); 
    cout<<s.getMax()<<" ";
    s.push(20); 
    cout<<s.getMax(); 
    
    return 0; 
}
4 19 19 19 20

Πρόγραμμα Java για παρακολούθηση τρέχοντος μέγιστου στοιχείου σε μια στοίβα

import java.util.*; 

class TrackMax{ 
  
    static class StackWithMax{  
        static Stack<Integer> mainStack = new Stack<Integer> ();  
      
        static Stack<Integer> trackStack = new Stack<Integer> ();  
      
    static void push(int x){  
            mainStack.push(x);
            
            if(mainStack.size() == 1){  
                trackStack.push(x);  
                return;  
            }  
      
            if(x > trackStack.peek()){  
                trackStack.push(x);  
            }
            
            else{
                trackStack.push(trackStack.peek());  
            }
        }  
      
        static int getMax(){  
            return trackStack.peek();  
        }  
      
        static void pop(){  
            mainStack.pop();  
            trackStack.pop();  
        }  
    };  
      
    public static void main(String[] args){  
        StackWithMax s = new StackWithMax();
        
        s.push(4);  
        System.out.print(s.getMax()+" ");  
        s.push(19);  
        System.out.print(s.getMax()+" ");  
        s.push(7);  
        System.out.print(s.getMax()+" "); 
        s.push(14);  
        System.out.print(s.getMax()+" ");  
        s.push(20);  
        System.out.print(s.getMax()); 
    } 
}
4 19 19 19 20

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

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

O (1), γιατί βρίσκουμε το μέγιστο σε σταθερό χρόνο.

Βλέπε επίσης
Συνολικοί αριθμοί χωρίς επαναλαμβανόμενα ψηφία σε εύρος

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

O (N), εδώ αντί να βρούμε το μέγιστο στοιχείο αποθηκεύουμε το μέγιστο στοιχείο τη στιγμή της εισαγωγής που μας έδωσε γραμμική πολυπλοκότητα χώρου.