טראַקינג קראַנט מאַקסימום עלעמענט אין אַ אָנלייגן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין פאַקסעט פאָורקיטעס ינפאָסיס
אָנלייגן

פּראָבלעם סטאַטעמענט

"טראַקינג קראַנט מאַקסימום עלעמענט אין אַ אָנלייגן" שטאַטן אַז איר האָט אַ 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.

אין נאַיוו צוגאַנג, מיר האַלטן אַן עקסטרע צייַטווייַליק אָנלייגן וואָס איז געניצט צו געפֿינען די מאַקסימום. יעדער מאָל ווען מיר דאַרפֿן צו געפֿינען די מאַקסימום, מיר פאָרן אַלע עלעמענטן פון מאַינסטאַקק. אַזוי צו אַריבערפירן די עלעמענטן, מיר דאַרפֿן צו קנאַל זיי אויס פון די הויפּט אָנלייגן און שטופּן זיי אין די צייַטווייַליק אָנלייגן. אַזוי אַז נאָך טראַווערסינג אַלע די עלעמענטן, מיר קענען שטופּן זיי צוריק אין די הויפּט אָנלייגן. דעריבער, ווען מיר דאַרפֿן צו מאַקסימום ביז איצט, די אָפּעראַציע קאָס אַ לינעאַר צייט קאַמפּלעקסיטי פון O (N). אַזוי אויב מיר געפֿינען די מאַקסימום ביז יעדער עלעמענט, די גאַנץ צייט קאַמפּלעקסיטי איז אָ (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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), ווייַל מיר אַריבער אַלע די עלעמענטן אין די אָנלייגן פּער געטמאַקס () אָפּעראַציע.

ספעיס קאַמפּלעקסיטי

אָ (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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (1) ווייַל מיר געפֿינען די מאַקסימום אין קעסיידערדיק צייט.

ספעיס קאַמפּלעקסיטי

דאָ, אַנשטאָט פון דער מאַקסימום עלעמענט, מיר סטאָרד די מאַקסימום עלעמענט אין דער צייט פון ינפּוט, וואָס האָט אונדז לינעאַר פּלאַץ קאַמפּלעקסיטי.