Encuentre el máximo en una pila en O (1) tiempo y O (1) espacio adicional

Dada una pila de enteros. La tarea es diseñar una pila especial de modo que el elemento máximo se pueda encontrar en O(1) tiempo y O(1) espacio extra.
Ejemplos
 

Given Stack :
2
5
1
64   --> Maximum

So Output must be 64 when getMax() is called.

A continuación se muestran las diferentes funciones diseñadas para empujar y sacar elementos de la pila. 
Push(x) : Inserta x en la parte superior de la pila. 
 

  • Si la pila está vacía, inserte x en la pila y haga que maxEle sea igual a x.
  • Si la pila no está vacía, compare x con maxEle. Se presentan dos casos:
    • Si x es menor o igual que maxEle, simplemente inserte x.
    • Si x es mayor que maxEle, inserte (2*x – maxEle) en la pila y haga que maxEle sea igual a x. Por ejemplo, el maxEle anterior era 3. Ahora queremos insertar 4. Actualizamos maxEle como 4 e insertamos 2*4 – 3 = 5 en la pila.

Pop(): elimina un elemento de la parte superior de la pila. 
 

  • Retire el elemento de la parte superior. Sea y el elemento eliminado. Se presentan dos casos:
    • Si y es menor o igual que maxEle, el elemento máximo en la pila sigue siendo maxEle.
    • Si y es mayor que maxEle, el elemento máximo ahora se convierte en (2*maxEle – y), así que actualice (maxEle = 2*maxEle – y). Aquí es donde recuperamos el máximo anterior del máximo actual y su valor en la pila. Por ejemplo, deje que el elemento a eliminar sea 5 y maxEle sea 4. Eliminamos 5 y actualizamos maxEle como 2*4 – 5 = 3.

Puntos importantes: 
 

  • La pila no contiene el valor real de un elemento si es máximo hasta ahora.
  • El elemento máximo real siempre se almacena en maxEle

Ilustración 
 

empujar (x) 
 

  • Número a insertar: 3, la pila está vacía, así que inserte 3 en la pila y maxEle = 3.
  • Número a insertar: 5, la pila no está vacía, 5> maxEle, inserte (2*5-3) en la pila y maxEle = 5.
  • Número a insertar: 2, la pila no está vacía, 2< maxEle, inserte 2 en la pila y maxEle = 5.
  • Número a insertar: 1, la pila no está vacía, 1< maxEle, inserte 1 en la pila y maxEle = 5.

Estallido() 
 

  • Inicialmente, el elemento máximo maxEle en la pila es 5.
  • Número eliminado: 1, dado que 1 es menor que maxEle, simplemente extraiga 1. maxEle = 5.
  • Número eliminado: 2, 2<maxEle, por lo que el número eliminado es 2 y maxEle sigue siendo igual a 5.
  • Número eliminado: 7, 7> maxEle, el número original es maxEle, que es 5 y el nuevo maxEle = 2*5 – 7 = 3.

C++

// C++ program to implement a stack that supports
// getMaximum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
 
// A user defined stack that supports getMax() in
// addition to push() and pop()
struct MyStack {
    stack<int> s;
    int maxEle;
 
    // Prints maximum element of MyStack
    void getMax()
    {
        if (s.empty())
            cout << "Stack is empty\n";
 
        // variable maxEle stores the maximum element
        // in the stack.
        else
            cout << "Maximum Element in the stack is: "
                 << maxEle << "\n";
    }
 
    // Prints top element of MyStack
    void peek()
    {
        if (s.empty()) {
            cout << "Stack is empty ";
            return;
        }
 
        int t = s.top(); // Top element.
 
        cout << "Top Most Element is: ";
 
        // If t < maxEle means maxEle stores
        // value of t.
        (t > maxEle) ? cout << maxEle : cout << t;
    }
 
    // Remove the top element from MyStack
    void pop()
    {
        if (s.empty()) {
            cout << "Stack is empty\n";
            return;
        }
 
        cout << "Top Most Element Removed: ";
        int t = s.top();
        s.pop();
 
        // Maximum will change as the maximum element
        // of the stack is being removed.
        if (t > maxEle) {
            cout << maxEle << "\n";
            maxEle = 2 * maxEle - t;
        }
 
        else
            cout << t << "\n";
    }
 
    // Removes top element from MyStack
    void push(int x)
    {
        // Insert new number into the stack
        if (s.empty()) {
            maxEle = x;
            s.push(x);
            cout << "Number Inserted: " << x << "\n";
            return;
        }
 
        // If new number is greater than maxEle
        if (x > maxEle) {
            s.push(2 * x - maxEle);
            maxEle = x;
        }
 
        else
            s.push(x);
 
        cout << "Number Inserted: " << x << "\n";
    }
};
 
// Driver Code
int main()
{
    MyStack s;
    s.push(3);
    s.push(5);
    s.getMax();
    s.push(7);
    s.push(19);
    s.getMax();
    s.pop();
    s.getMax();
    s.pop();
    s.peek();
 
    return 0;
}

Java

// Java program to implement a stack that supports
// getMaximum() in O(1) time and O(1) extra space.
import java.util.*;
 
class GFG
{
 
// A user defined stack that supports getMax() in
// addition to push() and pop()
static class MyStack
{
    Stack<Integer> s = new Stack<Integer>();
    int maxEle;
 
    // Prints maximum element of MyStack
    void getMax()
    {
        if (s.empty())
            System.out.print("Stack is empty\n");
 
        // variable maxEle stores the maximum element
        // in the stack.
        else
            System.out.print("Maximum Element in" +
                        "the stack is: "+maxEle + "\n");
 
    }
 
    // Prints top element of MyStack
    void peek()
    {
        if (s.empty())
        {
             
            System.out.print("Stack is empty ");
            return;
        }
 
        int t = s.peek(); // Top element.
 
        System.out.print("Top Most Element is: ");
 
        // If t < maxEle means maxEle stores
        // value of t.
        if(t > maxEle)
            System.out.print(maxEle);
        else
            System.out.print(t);
    }
 
    // Remove the top element from MyStack
    void pop()
    {
        if (s.empty())
        {
            System.out.print("Stack is empty\n");
            return;
        }
 
        System.out.print("Top Most Element Removed: ");
        int t = s.peek();
        s.pop();
 
        // Maximum will change as the maximum element
        // of the stack is being removed.
        if (t > maxEle)
        {
            System.out.print(maxEle + "\n");
            maxEle = 2 * maxEle - t;
        }
 
        else
            System.out.print(t + "\n");
    }
 
    // Removes top element from MyStack
    void push(int x)
    {
        // Insert new number into the stack
        if (s.empty())
        {
            maxEle = x;
            s.push(x);
            System.out.print("Number Inserted: " + x + "\n");
            return;
        }
 
        // If new number is less than maxEle
        if (x > maxEle)
        {
            s.push(2 * x - maxEle);
            maxEle = x;
        }
 
        else
            s.push(x);
 
        System.out.print("Number Inserted: " + x + "\n");
    }
};
 
// Driver Code
public static void main(String[] args)
{
    MyStack s = new MyStack();
    s.push(3);
    s.push(5);
    s.getMax();
    s.push(7);
    s.push(19);
    s.getMax();
    s.pop();
    s.getMax();
    s.pop();
    s.peek();
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python 3

# Class to make a Node
class Node:
    #Constructor which assign argument to nade's value
    def __init__(self, value):
        self.value = value
        self.next = None
   
    # This method returns the string representation of the object.
    def __str__(self):
        return "Node({})".format(self.value)
     
    #  __repr__ is same as __str__
    __repr__ = __str__
   
 
class Stack:
    # Stack Constructor initialise top of stack and counter.
    def __init__(self):
        self.top = None
        self.count = 0
        self.maximum = None
         
    #This method returns the string representation of the object (stack).
    def __str__(self):
        temp=self.top
        out=[]
        while temp:
            out.append(str(temp.value))
            temp=temp.next
        out='\n'.join(out)
        return ('Top {} \n\nStack :\n{}'.format(self.top,out))
         
    #  __repr__ is same as __str__
    __repr__=__str__
     
    #This method is used to get minimum element of stack
    def getMax(self):
        if self.top is None:
            return "Stack is empty"
        else:
            print("Maximum Element in the stack is: {}" .format(self.maximum))
 
  
 
    # Method to check if Stack is Empty or not
    def isEmpty(self):
        # If top equals to None then stack is empty
        if self.top == None:
            return True
        else:
        # If top not equal to None then stack is empty
            return False
 
    # This method returns length of stack      
    def __len__(self):
        self.count = 0
        tempNode = self.top
        while tempNode:
            tempNode = tempNode.next
            self.count+=1
        return self.count
 
    # This method returns top of stack      
    def peek(self):
        if self.top is None:
            print ("Stack is empty")
        else:   
            if self.top.value > self.maximum:
                print("Top Most Element is: {}" .format(self.maximum))
            else:
                print("Top Most Element is: {}" .format(self.top.value))
 
    #This method is used to add node to stack
    def push(self,value):
        if self.top is None:
            self.top = Node(value)
            self.maximum = value
             
        elif value > self.maximum :
            temp = (2 * value) - self.maximum
            new_node = Node(temp)
            new_node.next = self.top
            self.top = new_node
            self.maximum = value
        else:
            new_node = Node(value)
            new_node.next = self.top
            self.top = new_node
        print("Number Inserted: {}" .format(value))
   
    #This method is used to pop top of stack
    def pop(self):
        if self.top is None:
            print( "Stack is empty")
        else:
            removedNode = self.top.value
            self.top = self.top.next
            if removedNode > self.maximum:
                print ("Top Most Element Removed :{} " .format(self.maximum))
                self.maximum = ( ( 2 * self.maximum ) - removedNode )
            else:
                print ("Top Most Element Removed : {}" .format(removedNode))
 
                 
             
     
 # Driver program to test above class 
stack = Stack()
 
stack.push(3)
stack.push(5)
stack.getMax()
stack.push(7)
stack.push(19)
stack.getMax()    
stack.pop()
stack.getMax()
stack.pop()
stack.peek()
 
# This code is contributed by Blinkii

C#

// C# program to implement a stack that supports
// getMaximum() in O(1) time and O(1) extra space.
using System;
using System.Collections.Generic;
 
class GFG
{
 
// A user defined stack that supports getMax() in
// addition to push() and pop()
public class MyStack
{
    public Stack<int> s = new Stack<int>();
    public int maxEle;
 
    // Prints maximum element of MyStack
    public void getMax()
    {
        if (s.Count == 0)
            Console.Write("Stack is empty\n");
 
        // variable maxEle stores the maximum element
        // in the stack.
        else
            Console.Write("Maximum Element in" +
                        "the stack is: "+maxEle + "\n");
 
    }
 
    // Prints top element of MyStack
    public void peek()
    {
        if (s.Count == 0)
        {
             
            Console.Write("Stack is empty ");
            return;
        }
 
        int t = s.Peek(); // Top element.
 
        Console.Write("Top Most Element is: ");
 
        // If t < maxEle means maxEle stores
        // value of t.
        if(t > maxEle)
            Console.Write(maxEle);
        else
            Console.Write(t);
    }
 
    // Remove the top element from MyStack
    public void pop()
    {
        if (s.Count == 0)
        {
            Console.Write("Stack is empty\n");
            return;
        }
 
        Console.Write("Top Most Element Removed: ");
        int t = s.Peek();
        s.Pop();
 
        // Maximum will change as the maximum element
        // of the stack is being removed.
        if (t > maxEle)
        {
            Console.Write(maxEle + "\n");
            maxEle = 2 * maxEle - t;
        }
 
        else
            Console.Write(t + "\n");
    }
 
    // Removes top element from MyStack
    public void push(int x)
    {
        // Insert new number into the stack
        if (s.Count == 0)
        {
            maxEle = x;
            s.Push(x);
            Console.Write("Number Inserted: " + x + "\n");
            return;
        }
 
        // If new number is less than maxEle
        if (x > maxEle)
        {
            s.Push(2 * x - maxEle);
            maxEle = x;
        }
 
        else
            s.Push(x);
 
        Console.Write("Number Inserted: " + x + "\n");
    }
};
 
// Driver Code
public static void Main(String[] args)
{
    MyStack s = new MyStack();
    s.push(3);
    s.push(5);
    s.getMax();
    s.push(7);
    s.push(19);
    s.getMax();
    s.pop();
    s.getMax();
    s.pop();
    s.peek();
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
    // Javascript program to implement a stack that supports
    // getMaximum() in O(1) time and O(1) extra space.
     
    let s = [];
    let maxEle;
  
    // Prints maximum element of MyStack
    function getMax()
    {
        if (s.length == 0)
            document.write("Stack is empty" + "</br>");
  
        // variable maxEle stores the maximum element
        // in the stack.
        else
            document.write("Maximum Element in " +
                        "the stack is: "+maxEle + "</br>");
  
    }
  
    // Prints top element of MyStack
    function peek()
    {
        if (s.length == 0)
        {
              
            document.write("Stack is empty ");
            return;
        }
  
        let t = s[s.length - 1]; // Top element.
  
        document.write("Top Most Element is: ");
  
        // If t < maxEle means maxEle stores
        // value of t.
        if(t > maxEle)
            document.write(maxEle);
        else
            document.write(t);
    }
  
    // Remove the top element from MyStack
    function pop()
    {
        if (s.length == 0)
        {
            document.write("Stack is empty" + "</br>");
            return;
        }
  
        document.write("Top Most Element Removed: ");
        let t = s[s.length - 1];
        s.pop();
  
        // Maximum will change as the maximum element
        // of the stack is being removed.
        if (t > maxEle)
        {
            document.write(maxEle + "</br>");
            maxEle = 2 * maxEle - t;
        }
  
        else
            document.write(t + "</br>");
    }
  
    // Removes top element from MyStack
    function push(x)
    {
        // Insert new number into the stack
        if (s.length == 0)
        {
            maxEle = x;
            s.push(x);
            document.write("Number Inserted: " + x + "</br>");
            return;
        }
  
        // If new number is less than maxEle
        if (x > maxEle)
        {
            s.push(2 * x - maxEle);
            maxEle = x;
        }
  
        else
            s.push(x);
  
        document.write("Number Inserted: " + x + "</br>");
    }
     
    push(3);
    push(5);
    getMax();
    push(7);
    push(19);
    getMax();
    pop();
    getMax();
    pop();
    peek();
     
    //  This code is contributed by rameshtravel07.
</script>
Producción: 

Number Inserted: 3
Number Inserted: 5
Maximum Element in the stack is: 5
Number Inserted: 7
Number Inserted: 19
Maximum Element in the stack is: 19
Top Most Element Removed: 19
Maximum Element in the stack is: 7
Top Most Element Removed: 7
Top Most Element is: 5

 

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

Publicación traducida automáticamente

Artículo escrito por krikti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *