스택에서 현재 최대 요소 추적

난이도 쉽게
자주 묻는 질문 팩트 셋 포카이트 인포시스
스택조회수 52

문제 정책

"스택의 현재 최대 요소 추적"은 스택 데이터 구조. 현재 인덱스까지 스택의 최대 값을 추적하는 함수를 만듭니다.

스택에서 현재 최대 요소 추적

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), 여기서 최대 요소를 찾는 대신 입력 시점에 최대 요소를 저장하여 선형 공간 복잡성을 제공합니다.

Translate »