Следење на тековниот максимален елемент во оџак


Ниво на тешкотија Лесно
Често прашувано во Факти Фуркити Infosys
Магацинот

Изјава за проблем

„Следење на тековниот максимален елемент во магацинот“ наведува дека ви е дадена a магацинот структура на податоци. Создадете функција за да ја следите максималната вредност во оџакот до моменталниот индекс.

Следење на тековниот максимален елемент во оџак

пример

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

Јава програма за следење на тековниот максимален елемент во оџак

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

Јава програма за следење на тековниот максимален елемент во оџак

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), затоа што го наоѓаме максимумот во константно време.

Комплексноста на просторот

O (N), овде наместо да го најдеме максималниот елемент, ние го зачувуваме максималниот елемент во времето на внесување што ни даде линеарна просторна сложеност.