ຕິດຕາມ Element ສູງສຸດໃນປະຈຸບັນໃນ Stack


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ປັດໃຈ ສີ່ພັນ Infosys
Stack

ຖະແຫຼງການບັນຫາ

“ ການຕິດຕາມອົງປະກອບສູງສຸດໃນປະຈຸບັນຢູ່ໃນສະເຕກ” ກ່າວວ່າທ່ານໄດ້ຖືກມອບໃຫ້ stack ໂຄງສ້າງຂໍ້ມູນ. ສ້າງ ໜ້າ ທີ່ເພື່ອໃຫ້ຕິດຕາມມູນຄ່າສູງສຸດໃນກະແສຈົນຮອດດັດສະນີປັດຈຸບັນ.

ຕິດຕາມ Element ສູງສຸດໃນປະຈຸບັນໃນ Stack

ຍົກຕົວຢ່າງ

4 19 7 14 20
4 19 19 19 20

ຄໍາອະທິບາຍ: ຄຸນຄ່າສູງສຸດຈົນກ່ວາຕົວຊີ້ວັດໃນປະຈຸບັນຈະຖືກພິມແລະພວກມັນຖືກສະແດງຢູ່ໃນຮູບຂ້າງເທິງ. ດັ່ງທີ່ພວກເຮົາພົບກັບ ຈຳ ນວນ ໜຶ່ງ ເຊິ່ງໃຫຍ່ກວ່າ ຈຳ ນວນສູງສຸດໃນປະຈຸບັນ. ມູນຄ່າຂອງການປ່ຽນແປງສູງສຸດໃນປະຈຸບັນ.

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

ວິທີການ Naive

ລະບົບວິເຄາະ

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 ++ Program ສຳ ລັບຕິດຕາມ Element ສູງສຸດໃນປະຈຸບັນໃນ Stack

#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 Program ສຳ ລັບຕິດຕາມ Element ສູງສຸດໃນປະຈຸບັນໃນ Stack

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), ເນື່ອງຈາກວ່າພວກເຮົາຜ່ານອົງປະກອບທັງ ໝົດ ພາຍໃນ stack ຕໍ່ getmax () ການ ດຳ ເນີນງານ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງໃຊ້ stack ຊົ່ວຄາວເພື່ອເກັບສ່ວນປະກອບຂອງ stack ຕົ້ນຕໍ.

ວິທີການທີ່ມີປະສິດຕິພາບ

ລະບົບວິເຄາະ

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 ++ Program ສຳ ລັບຕິດຕາມ Element ສູງສຸດໃນປະຈຸບັນໃນ Stack

#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 Program ສຳ ລັບຕິດຕາມ Element ສູງສຸດໃນປະຈຸບັນໃນ Stack

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), ໃນທີ່ນີ້ແທນທີ່ຈະຊອກຫາອົງປະກອບສູງສຸດທີ່ພວກເຮົາ ກຳ ລັງເກັບຮັກສາອົງປະກອບສູງສຸດໃນເວລາປ້ອນຂໍ້ມູນເຊິ່ງເຮັດໃຫ້ພວກເຮົາມີຄວາມສັບສົນໃນອະວະກາດ.