Отслеживание текущего максимального элемента в стеке


Сложный уровень Легко
Часто спрашивают в Набор фактов Фуркиты Infosys
Стек

Постановка задачи

«Отслеживание текущего максимального элемента в стеке» означает, что вам дается стек структура данных. Создайте функцию для отслеживания максимального значения в стеке до текущего индекса.

Отслеживание текущего максимального элемента в стеке

Пример

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), здесь вместо нахождения максимального элемента мы сохраняем максимальный элемент во время ввода, что дало нам линейную пространственную сложность.