Encuentre el máximo en la pila en O (1) sin usar una pila adicional

La tarea es diseñar una pila que pueda obtener el valor máximo en la pila en tiempo O(1) sin usar una pila adicional.

Ejemplos: 

Entrada: 
push(2) 
findMax() 
push(6) 
findMax() 
pop() 
findMax() 
Salida: 
2 insertados en la pila 
Valor máximo en la pila: 2 
6 insertados en la pila 
Valor máximo en la pila: 6 
Elemento extraído 
Valor máximo en la pila: 2 

Enfoque: en lugar de empujar un solo elemento a la pila, empuja un par en su lugar. El par consta de (valor, localMax) donde localMax es el valor máximo hasta ese elemento.  

  • Cuando insertamos un nuevo elemento, si el nuevo elemento es mayor que el máximo local debajo de él, establecemos el máximo local de un nuevo elemento igual al elemento mismo.
  • De lo contrario, establecemos el máximo local del nuevo elemento igual al máximo local del elemento debajo de él.
  • El máximo local de la parte superior de la pila será el máximo general.
  • Ahora, si queremos saber el máximo en cualquier punto dado, le preguntamos a la parte superior de la pila por el máximo local asociado con él, lo que se puede hacer en O(1).

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

C++

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
struct Block {
 
    // A block has two elements
    // as components
    int value, localMax;
};
 
class Stack {
 
private:
    // Pointer of type block,
    // Will be useful later as the
    // size can be dynamically allocated
    struct Block* S;
    int size, top;
 
public:
    Stack(int);
    void push(int);
    void pop();
    void max();
};
 
Stack::Stack(int n)
{
 
    // Setting size of stack and
    // initial value of top
    size = n;
    S = new Block[n];
    top = -1;
}
 
// Function to push an element to the stack
void Stack::push(int n)
{
 
    // Doesn't allow pushing elements
    // if stack is full
    if (top == size - 1) {
        cout << "Stack is full" << endl;
    }
    else {
        top++;
 
        // If the inserted element is the first element
        // then it is the maximum element, since no other
        // elements is in the stack, so the localMax
        // of the first element is the element itself
        if (top == 0) {
            S[top].value = n;
            S[top].localMax = n;
        }
        else {
 
            // If the newly pushed element is
            // less than the localMax of element below it,
            // Then the over all maximum doesn't change
            // and hence, the localMax of the newly inserted
            // element is same as element below it
            if (S[top - 1].localMax > n) {
                S[top].value = n;
                S[top].localMax = S[top - 1].localMax;
            }
 
            // Newly inserted element is greater than the localMax
            // below it, hence the localMax of new element
            // is the element itself
            else {
                S[top].value = n;
                S[top].localMax = n;
            }
        }
 
        cout << n << " inserted in stack" << endl;
    }
}
 
// Function to remove an element
// from the top of the stack
void Stack::pop()
{
 
    // If stack is empty
    if (top == -1) {
        cout << "Stack is empty" << endl;
    }
 
    // Remove the element if the stack
    // is not empty
    else {
        top--;
        cout << "Element popped" << endl;
    }
}
 
// Function to find the maximum
// element from the stack
void Stack::max()
{
 
    // If stack is empty
    if (top == -1) {
        cout << "Stack is empty" << endl;
    }
    else {
 
        // The overall maximum is the local maximum
        // of the top element
        cout << "Maximum value in the stack: "
             << S[top].localMax << endl;
    }
}
 
// Driver code
int main()
{
 
    // Create stack of size 5
    Stack S1(5);
 
    S1.push(2);
    S1.max();
    S1.push(6);
    S1.max();
    S1.pop();
    S1.max();
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
static class Block
{
 
    // A block has two elements
    // as components
    int value, localMax;
};
 
static class Stack
{
 
    // Pointer of type block,
    // Will be useful later as the
    // size can be dynamically allocated
    Block S[];
    int size, top;
 
 
Stack(int n)
{
 
    // Setting size of stack and
    // initial value of top
    size = n;
    S = new Block[n];
    for(int i=0;i<n;i++)S[i]=new Block();
    top = -1;
}
 
// Function to push an element to the stack
void push(int n)
{
 
    // Doesn't allow pushing elements
    // if stack is full
    if (top == size - 1)
    {
        System.out.print( "Stack is full" );
    }
    else
    {
        top++;
 
        // If the inserted element is the first element
        // then it is the maximum element, since no other
        // elements is in the stack, so the localMax
        // of the first element is the element itself
        if (top == 0)
        {
            S[top].value = n;
            S[top].localMax = n;
        }
        else
        {
 
            // If the newly pushed element is
            // less than the localMax of element below it,
            // Then the over all maximum doesn't change
            // and hence, the localMax of the newly inserted
            // element is same as element below it
            if (S[top - 1].localMax > n)
            {
                S[top].value = n;
                S[top].localMax = S[top - 1].localMax;
            }
 
            // Newly inserted element is greater than the localMax
            // below it, hence the localMax of new element
            // is the element itself
            else
            {
                S[top].value = n;
                S[top].localMax = n;
            }
        }
 
        System.out.println( n + " inserted in stack" );
    }
}
 
// Function to remove an element
// from the top of the stack
void pop()
{
 
    // If stack is empty
    if (top == -1)
    {
        System.out.println( "Stack is empty");
    }
 
    // Remove the element if the stack
    // is not empty
    else
    {
        top--;
        System.out.println( "Element popped" );
    }
}
 
// Function to find the maximum
// element from the stack
void max()
{
 
    // If stack is empty
    if (top == -1)
    {
        System.out.println( "Stack is empty");
    }
    else
    {
 
        // The overall maximum is the local maximum
        // of the top element
        System.out.println( "Maximum value in the stack: "+
                                            S[top].localMax);
    }
}
}
 
// Driver code
public static void main(String args[])
{
 
    // Create stack of size 5
    Stack S1=new Stack(5);
 
    S1.push(2);
    S1.max();
    S1.push(6);
    S1.max();
    S1.pop();
    S1.max();
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach
class Block:
     
    # A block has two elements
    # as components  (i.e. value and localMax)
    def __init__(self, value, localMax):
        self.value = value
        self.localMax = localMax
 
class Stack:
    def __init__(self, size):
         
        # Setting size of stack and
        # initial value of top
        self.stack = [None] * size
        self.size = size
        self.top = -1
 
    # Function to push an element
    # to the stack
    def push(self, value):
 
        # Don't allow pushing elements
        # if stack is full
        if self.top == self.size - 1:
            print("Stack is full")
        else:
            self.top += 1
             
            # If the inserted element is the first element
            # then it is the maximum element, since no other
            # elements is in the stack, so the localMax
            # of the first element is the element itself
            if self.top == 0:
                self.stack[self.top] = Block(value, value)
 
            else:
                 
                # If the newly pushed element is less
                # than the localMax of element below it,
                # Then the over all maximum doesn't change
                # and hence, the localMax of the newly inserted
                # element is same as element below it
                if self.stack[self.top - 1].localMax > value:
                    self.stack[self.top] = Block(
                        value, self.stack[self.top - 1].localMax)
 
                # Newly inserted element is greater than
                # the localMax below it, hence the localMax
                # of new element is the element itself
                else:
                    self.stack
                    self.stack[self.top] = Block(value, value)
                     
            print(value, "inserted in the stack")
             
    # Function to remove an element 
    # from the top of the stack         
    def pop(self):
         
        # If stack is empty
        if self.top == -1:
            print("Stack is empty")
 
        # Remove the element if the stack
        # is not empty
        else:
            self.top -= 1
            print("Element popped")
             
    # Function to find the maximum 
    # element from the stack 
    def max(self):
         
        # If stack is empty
        if self.top == -1:
            print("Stack is empty")
        else:
             
            # The overall maximum is the local maximum
            # of the top element
            print("Maximum value in the stack:",
                  self.stack[self.top].localMax)
 
# Driver code
 
# Create stack of size 5
stack = Stack(5)
stack.push(2)
stack.max()
stack.push(6)
stack.max()
stack.pop()
stack.max()
 
# This code is contributed by girishthatte

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
public class Block
{
 
    // A block has two elements
    // as components
    public int value, localMax;
};
 
public class Stack
{
 
    // Pointer of type block,
    // Will be useful later as the
    // size can be dynamically allocated
    public Block []S;
    public int size, top;
 
 
public Stack(int n)
{
 
    // Setting size of stack and
    // initial value of top
    size = n;
    S = new Block[n];
    for(int i = 0; i < n; i++)S[i] = new Block();
    top = -1;
}
 
// Function to push an element to the stack
public void push(int n)
{
 
    // Doesn't allow pushing elements
    // if stack is full
    if (top == size - 1)
    {
        Console.Write( "Stack is full" );
    }
    else
    {
        top++;
 
        // If the inserted element is the first element
        // then it is the maximum element, since no other
        // elements is in the stack, so the localMax
        // of the first element is the element itself
        if (top == 0)
        {
            S[top].value = n;
            S[top].localMax = n;
        }
        else
        {
 
            // If the newly pushed element is
            // less than the localMax of element below it,
            // Then the over all maximum doesn't change
            // and hence, the localMax of the newly inserted
            // element is same as element below it
            if (S[top - 1].localMax > n)
            {
                S[top].value = n;
                S[top].localMax = S[top - 1].localMax;
            }
 
            // Newly inserted element is greater than the localMax
            // below it, hence the localMax of new element
            // is the element itself
            else
            {
                S[top].value = n;
                S[top].localMax = n;
            }
        }
 
        Console.WriteLine( n + " inserted in stack" );
    }
}
 
// Function to remove an element
// from the top of the stack
public void pop()
{
 
    // If stack is empty
    if (top == -1)
    {
        Console.WriteLine( "Stack is empty");
    }
 
    // Remove the element if the stack
    // is not empty
    else
    {
        top--;
        Console.WriteLine( "Element popped" );
    }
}
 
// Function to find the maximum
// element from the stack
public void max()
{
 
    // If stack is empty
    if (top == -1)
    {
        Console.WriteLine( "Stack is empty");
    }
    else
    {
 
        // The overall maximum is the local maximum
        // of the top element
        Console.WriteLine( "Maximum value in the stack: "+
                                            S[top].localMax);
    }
}
}
 
// Driver code
public static void Main(String []args)
{
 
    // Create stack of size 5
    Stack S1 = new Stack(5);
 
    S1.push(2);
    S1.max();
    S1.push(6);
    S1.max();
    S1.pop();
    S1.max();
}
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
 
/// JavaScript implementation of the approach
class Block{
 
    /// A block has two elements
    /// as components (i.e. value and localMax)
    constructor(value, localMax){
        this.value = value
        this.localMax = localMax
    }
}
 
class Stack{
    constructor(size){
         
        /// Setting size of stack and
        /// initial value of top
        this.stack = new Array(size).fill(null)
        this.size = size
        this.top = -1
    }
 
    // Function to push an element
    // to the stack
    push(value){
 
        // Don't allow pushing elements
        // if stack is full
        if(this.top == this.size - 1)
            document.write("Stack is full","</br>")
        else{
            this.top += 1
             
            // If the inserted element is the first element
            // then it is the maximum element, since no other
            // elements is in the stack, so the localMax
            // of the first element is the element itthis
            if(this.top == 0)
                this.stack[this.top] = new Block(value, value)
 
            else{
                 
                // If the newly pushed element is less
                // than the localMax of element below it,
                // Then the over all maximum doesn't change
                // and hence, the localMax of the newly inserted
                // element is same as element below it
                if(this.stack[this.top - 1].localMax > value){
                    this.stack[this.top] = new Block(
                        value, this.stack[this.top - 1].localMax)
                    }
 
                // Newly inserted element is greater than
                // the localMax below it, hence the localMax
                // of new element is the element itthis
                else{
                    this.stack[this.top] = new Block(value, value)
                }
            }
                     
            document.write(value, "inserted in the stack","</br>")
        }
    }
             
    // Function to remove an element
    // from the top of the stack       
    pop(){
         
        // If stack is empty
        if(this.top == -1)
            document.write("Stack is empty","</br>")
 
        // Remove the element if the stack
        // is not empty
        else{
            this.top -= 1
            document.write("Element popped","</br>")
        }
    }
             
    // Function to find the maximum
    // element from the stack
    max(){
         
        // If stack is empty
        if(this.top == -1)
            document.write("Stack is empty","</br>")
        else{
             
            // The overall maximum is the local maximum
            // of the top element
            document.write("Maximum value in the stack:",this.stack[this.top].localMax,"</br>")
        }
    }
}
 
// Driver code
 
// Create stack of size 5
let stack = new Stack(5)
stack.push(2)
stack.max()
stack.push(6)
stack.max()
stack.pop()
stack.max()
 
/// This code is contributed by shinjanpatra
 
</script>
Producción: 

2 inserted in stack
Maximum value in the stack: 2
6 inserted in stack
Maximum value in the stack: 6
Element popped
Maximum value in the stack: 2

 

Complejidad de tiempo : O(1)

Espacio Auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por RuchaDeodhar 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 *