מעקב אחר אלמנט מרבי הנוכחי בערימה


רמת קושי קַל
נשאל לעתים קרובות סט עובדות פורקיטים אינפוסיס
לערום

הצהרת בעיה

"מעקב אחר אלמנט מרבי זרם בערימה" קובע כי ניתן לך לערום מבנה נתונים. צור פונקציה כדי לעקוב אחר הערך המרבי בערימה עד לאינדקס הנוכחי.

מעקב אחר אלמנט מרבי הנוכחי בערימה

דוגמה

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).

קופונים

תכנית 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

ניתוח מורכבות

מורכבות זמן

O (N) מכיוון שאנחנו חוצים את כל האלמנטים בתוך הערימה לכל פעולת getmax ().

מורכבות בחלל

O (N) מכיוון שאנחנו משתמשים בערימה זמנית לאחסון האלמנטים של הערימה הראשית.

שיטה יעילה

אַלגוֹרִיתְם

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), כאן במקום למצוא את האלמנט המרבי אנו מאחסנים את האלמנט המרבי בזמן הקלט אשר נתן לנו מורכבות שטח ליניארית.