Seguimiento del elemento máximo actual en una pila

Dada una pila, realice un seguimiento del valor máximo que contiene. El valor máximo puede ser el elemento superior de la pila, pero una vez que se inserta un elemento nuevo o se extrae un elemento de la pila, el elemento máximo será ahora del resto de los elementos.

Ejemplos: 

Entrada: 4 19 7 14 20
Salida: Los valores máximos en la pila son 

         4 19 19 19 20

Entrada: 40 19 7 14 20 5
Salida:  Los valores máximos en la pila son 

         40 40 40 40 40 40

Método 1 (Fuerza bruta) : 

Seguimos empujando los elementos en la pila principal y cada vez que se nos pide devolver el elemento máximo, recorremos la pila e imprimimos el elemento máximo.

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(1)

Método 2 (eficiente) : un enfoque eficiente sería mantener una pila auxiliar mientras se empuja el elemento en la pila principal. Esta pila auxiliar hará un seguimiento del elemento máximo. 

A continuación se muestra el algoritmo paso a paso para hacer esto : 

1. Cree una pila auxiliar, diga ‘trackStack’ para realizar un seguimiento del elemento máximo
2. Empuje el primer elemento a mainStack y trackStack. 
3. Ahora, desde el segundo elemento, empuje el elemento a la pila principal. Compare el elemento con el elemento superior de la pila de pistas, si el elemento actual es mayor que la parte superior de la pila de pistas, empuje el elemento actual a la pila de pistas; de lo contrario, vuelva a colocar el elemento superior de la pila de pistas. 
4. Si extraemos un elemento de la pila principal, también extraemos un elemento del trackStack. 
5. Ahora, para calcular el máximo de la pila principal en cualquier punto, simplemente podemos imprimir el elemento superior de la pila de pistas. 

Explicación paso a paso: 

Suponga que los elementos se colocan en la pila en el orden {4, 2, 14, 1, 18} 

• Paso 1: Empuje 4, Corriente máxima: 4 
• Paso 2: Empuje 2, Corriente máxima: 4 
• Paso 3: Empuje 14, corriente máxima: 14 
• Paso 4: Empuje 1, Corriente máxima: 14 
• Paso 5: Empuje 18, Corriente máxima: 18 
• Paso 6: Pop 18, corriente máxima: 14

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to keep track of maximum
// element in a stack
#include <bits/stdc++.h>
using namespace std;
 
class StackWithMax
{
    // main stack
    stack<int> mainStack;
 
    // stack to keep track of max element
    stack<int> trackStack;
 
public:
    void push(int x)
    {
        mainStack.push(x);
        if (mainStack.size() == 1)
        {
            trackStack.push(x);
            return;
        }
 
        // If current element is greater than
        // the top element of track stack, push
        // the current element to track stack
        // otherwise push the element at top of
        // track stack again into it.
        if (x > trackStack.top())
            trackStack.push(x);
        else
            trackStack.push(trackStack.top());
    }
 
    int getMax()
    {
        return trackStack.top();
    }
 
    int pop()
    {
        mainStack.pop();
        trackStack.pop();
    }
};
 
// Driver program to test above functions
int main()
{
    StackWithMax s;
    s.push(20);
    cout << s.getMax() << endl;
    s.push(10);
    cout << s.getMax() << endl;
    s.push(50);
    cout << s.getMax() << endl;
    return 0;
}

// Java program to keep track of maximum
// element in a stack
import java.util.*;
class GfG {
 
static class StackWithMax
{
    // main stack
    static Stack<Integer> mainStack = new Stack<Integer> ();
 
    // Stack to keep track of max element
    static Stack<Integer> trackStack = new Stack<Integer> ();
 
static void push(int x)
    {
        mainStack.push(x);
        if (mainStack.size() == 1)
        {
            trackStack.push(x);
            return;
        }
 
        // If current element is greater than
        // the top element of track stack, push
        // the current element to track stack
        // otherwise push the element at top of
        // track stack again into it.
        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();
    }
};
 
// Driver program to test above functions
public static void main(String[] args)
{
    StackWithMax s = new StackWithMax();
    s.push(20);
    System.out.println(s.getMax());
    s.push(10);
    System.out.println(s.getMax());
    s.push(50);
    System.out.println(s.getMax());
}
}

# Python3 program to keep track of
# maximum element in a stack
 
class StackWithMax:
    def __init__(self):
         
        # main stack
        self.mainStack = []
     
        # stack to keep track of
        # max element
        self.trackStack = []
 
    def push(self, x):
        self.mainStack.append(x)
        if (len(self.mainStack) == 1):
            self.trackStack.append(x)
            return
 
        # If current element is greater than
        # the top element of track stack,
        # append the current element to track
        # stack otherwise append the element
        # at top of track stack again into it.
        if (x > self.trackStack[-1]):
            self.trackStack.append(x)
        else:
            self.trackStack.append(self.trackStack[-1])
 
    def getMax(self):
        return self.trackStack[-1]
 
    def pop(self):
        self.mainStack.pop()
        self.trackStack.pop()
 
# Driver Code
if __name__ == '__main__':
 
    s = StackWithMax()
    s.push(20)
    print(s.getMax())
    s.push(10)
    print(s.getMax())
    s.push(50)
    print(s.getMax())
 
# This code is contributed by PranchalK

// C# program to keep track of maximum
// element in a stack
using System;
using System.Collections.Generic;
 
class GfG
{
 
public class StackWithMax
{
    // main stack
    static Stack<int> mainStack = new Stack<int> ();
 
    // stack to keep track of max element
    static Stack<int> trackStack = new Stack<int> ();
 
    public void push(int x)
    {
        mainStack.Push(x);
        if (mainStack.Count == 1)
        {
            trackStack.Push(x);
            return;
        }
 
        // If current element is greater than
        // the top element of track stack, push
        // the current element to track stack
        // otherwise push the element at top of
        // track stack again into it.
        if (x > trackStack.Peek())
            trackStack.Push(x);
        else
            trackStack.Push(trackStack.Peek());
    }
 
    public int getMax()
    {
        return trackStack.Peek();
    }
 
    public void pop()
    {
        mainStack.Pop();
        trackStack.Pop();
    }
};
 
// Driver code
public static void Main()
{
    StackWithMax s = new StackWithMax();
    s.push(20);
    Console.WriteLine(s.getMax());
    s.push(10);
    Console.WriteLine(s.getMax());
    s.push(50);
    Console.WriteLine(s.getMax());
}
}
 
/* This code contributed by PrinciRaj1992 */

<script>
    // Javascript program to keep track of maximum
    // element in a stack
     
    // main stack
    let mainStack = [];
   
    // stack to keep track of max element
    let trackStack = [];
   
    function push(x)
    {
        mainStack.push(x);
        if (mainStack.length == 1)
        {
            trackStack.push(x);
            return;
        }
   
        // If current element is greater than
        // the top element of track stack, push
        // the current element to track stack
        // otherwise push the element at top of
        // track stack again into it.
        if (x > trackStack[trackStack.length - 1])
            trackStack.push(x);
        else
            trackStack.push(trackStack[trackStack.length - 1]);
    }
   
    function getMax()
    {
        return trackStack[trackStack.length - 1];
    }
   
    function pop()
    {
        mainStack.pop();
        trackStack.pop();
    }
     
    push(20);
    document.write(getMax() + "</br>");
    push(10);
    document.write(getMax() + "</br>");
    push(50);
    document.write(getMax());
     
    // This code is contributed by rameshtravel07.
</script>

20
20
50

Complejidad temporal : O(1) 
Complejidad auxiliar: O(n)

Este artículo es una contribución de Rohit . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.