การติดตามองค์ประกอบสูงสุดในปัจจุบันในกอง


ระดับความยาก สะดวกสบาย
ถามบ่อยใน ข้อเท็จจริง โฟร์ไคต์ อินโฟซิส
กอง

คำชี้แจงปัญหา

“ การติดตามองค์ประกอบสูงสุดในปัจจุบันในกลุ่ม” ระบุว่าคุณจะได้รับไฟล์ กอง โครงสร้างข้อมูล. สร้างฟังก์ชันเพื่อติดตามค่าสูงสุดในสแต็กจนถึงดัชนีปัจจุบัน

การติดตามองค์ประกอบสูงสุดในปัจจุบันในกอง

ตัวอย่าง

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

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

บน), เนื่องจากเราสำรวจองค์ประกอบทั้งหมดภายในสแต็กต่อการดำเนินการ 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

โปรแกรม 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) ที่นี่แทนที่จะค้นหาองค์ประกอบสูงสุดที่เรากำลังจัดเก็บองค์ประกอบสูงสุดในเวลาที่ป้อนข้อมูลซึ่งทำให้เรามีความซับซ้อนของพื้นที่เชิงเส้น