ردیابی حداکثر عنصر فعلی در پشته


سطح دشواری ساده
اغلب در واقعیت فورکایت 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

تحلیل پیچیدگی

پیچیدگی زمان

O (1) ، زیرا ما در زمان ثابت حداکثر را پیدا می کنیم.

پیچیدگی فضا

O (N) ، در اینجا به جای یافتن حداکثر عنصر ، ما حداکثر عنصر را در زمان ورودی ذخیره می کنیم که به ما پیچیدگی فضای خطی می دهد.