diseñar una pila tal que getMinimum () sea O (1)

Esta es una de las preguntas de una entrevista. Necesita diseñar una pila que contenga un valor entero tal que la función getMinimum () debería devolver el elemento mínimo en la pila.

Por ejemplo: considere el siguiente ejemplo

caso 1

5 -> ARRIBA
1
4
6
2

Cuando se llama a getMinimum (), debe devolver 1, que es el elemento mínimo 
en la pila. 

caso # 2

stack.pop ()
stack.pop ()

Nota: Tanto el 5 como el 1 se extraen de la pila. Entonces, después de esto, la pila
parece,

4 -> ARRIBA
6
2

Cuando se llama a getMinimum (), debe devolver 2, que es el mínimo en el 
apilar.

Constriantes:

1. getMinimum debería devolver el valor mínimo en O (1)
2. La restricción de espacio también debe tenerse en cuenta al diseñarlo y, si usa espacio adicional, debe ser de espacio constante.

EDITAR: Esto falla en la restricción de "espacio constante" - básicamente duplica el espacio requerido. Sin embargo, dudo mucho que haya una solución que no haga eso, sin arruinar la complejidad del tiempo de ejecución en alguna parte (por ejemplo, hacer push / pop O (n)). Tenga en cuenta que esto no cambia la complejidad del espacio requerido, por ejemplo, si tiene una pila con requisitos de espacio O (n), seguirá siendo O (n) solo con un factor constante diferente.

Solución de espacio no constante

Mantenga una pila "duplicada" de "el mínimo de todos los valores inferiores en la pila". Cuando saque la pila principal, saque también la pila mínima. Cuando empuja la pila principal, empuja el nuevo elemento o el mínimo actual, el que sea menor. getMinimum()luego se implementa como just minStack.peek().

Entonces, usando su ejemplo, tendríamos:

Real stack        Min stack

5  --> TOP        1
1                 1
4                 2
6                 2
2                 2

Después de hacer estallar dos veces, obtienes:

Real stack        Min stack

4                 2
6                 2
2                 2

Avíseme si esto no es suficiente información. Es simple cuando lo asimilas, pero al principio puede ser necesario rascarte un poco la cabeza :)

(La desventaja, por supuesto, es que duplica el requisito de espacio. Sin embargo, el tiempo de ejecución no sufre significativamente, es decir, sigue siendo la misma complejidad).

EDITAR: Hay una variación que es un poco más complicada, pero tiene mejor espacio en general. Todavía tenemos la pila mínima, pero solo salimos de ella cuando el valor que sacamos de la pila principal es igual al de la pila mínima. Solo empujamos a la pila mínima cuando el valor que se empuja a la pila principal es menor o igual que el valor mínimo actual. Esto permite valores mínimos duplicados. getMinimum()sigue siendo sólo una operación mínima. Por ejemplo, tomando la versión original y presionando 1 nuevamente, obtendríamos:

Real stack        Min stack

1  --> TOP        1
5                 1
1                 2
4                 
6                 
2                 

Saliendo de los salientes anteriores de ambas pilas porque 1 == 1, dejando:

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2                 

Salir de nuevo solo aparece en la pila principal, porque 5> 1:

Real stack        Min stack

1                 1
4                 2
6                 
2                 

Al volver a aparecer, aparecen ambas pilas porque 1 == 1:

Real stack        Min stack

4                 2
6                 
2                 

Esto termina con la misma complejidad de espacio en el peor de los casos (el doble de la pila original) pero mucho mejor uso del espacio si rara vez obtenemos un "nuevo mínimo o igual".

EDITAR: Aquí hay una implementación del esquema malvado de Pete. No lo he probado a fondo, pero creo que está bien :)

using System.Collections.Generic;

public class FastMinStack<T>
{
    private readonly Stack<T> stack = new Stack<T>();
    // Could pass this in to the constructor
    private readonly IComparer<T> comparer = Comparer<T>.Default;

    private T currentMin;

    public T Minimum
    {
        get { return currentMin; }
    }

    public void Push(T element)
    {
        if (stack.Count == 0 ||
            comparer.Compare(element, currentMin) <= 0)
        {
            stack.Push(currentMin);
            stack.Push(element);
            currentMin = element;
        }
        else
        {
            stack.Push(element);
        }
    }

    public T Pop()
    {
        T ret = stack.Pop();
        if (comparer.Compare(ret, currentMin) == 0)
        {
            currentMin = stack.Pop();
        }
        return ret;
    }
}

Agregue un campo para mantener el valor mínimo y actualizarlo durante Pop () y Push (). De esa forma, getMinimum () será O (1), pero Pop () y Push () tendrán que trabajar un poco más.

Si se muestra el valor mínimo, Pop () será O (n); de lo contrario, ambos seguirán siendo O (1). Al cambiar el tamaño, Push () se convierte en O (n) según la implementación de Stack.

Aquí hay una implementación rápida

public sealed class MinStack {
    private int MinimumValue;
    private readonly Stack<int> Stack = new Stack<int>();

    public int GetMinimum() {
        if (IsEmpty) {
            throw new InvalidOperationException("Stack is empty");
        }
        return MinimumValue;
    }

    public int Pop() {
        var value = Stack.Pop();
        if (value == MinimumValue) {
            MinimumValue = Stack.Min();
        }
        return value;
    }

    public void Push(int value) {
        if (IsEmpty || value < MinimumValue) {
            MinimumValue = value;
        }
        Stack.Push(value);
    }

    private bool IsEmpty { get { return Stack.Count() == 0; } }
}

public class StackWithMin {
    int min;
    int size;
    int[] data = new int[1024];

    public void push ( int val ) {
        if ( size == 0 ) {
            data[size] = val;
            min = val;
        } else if ( val < min) {
            data[size] = 2 * val - min;
            min = val;

            assert (data[size] < min); 
        } else {
            data[size] = val;
        }

        ++size;

        // check size and grow array
    }

    public int getMin () {
        return min;
    }

    public int pop () {
        --size;

        int val = data[size];

        if ( ( size > 0 ) && ( val < min ) ) {
            int prevMin = min;
            min += min - val;
            return prevMin;
        } else {
            return val;
        }
    }

    public boolean isEmpty () {
        return size == 0;
    }

    public static void main (String...args) {
        StackWithMin stack = new StackWithMin();

        for ( String arg: args ) 
            stack.push( Integer.parseInt( arg ) );

        while ( ! stack.isEmpty() ) {
            int min = stack.getMin();
            int val = stack.pop();

            System.out.println( val + " " + min );
        }

        System.out.println();
    }

}

Almacena el mínimo actual explícitamente, y si el mínimo cambia, en lugar de presionar el valor, empuja un valor con la misma diferencia al otro lado del nuevo mínimo (si min = 7 y usted presiona 5, presiona 3 en su lugar (5- | 7-5 | = 3) y establece min en 5; si luego saca 3 cuando min es 5, ve que el valor emergente es menor que min, por lo que invierte el procedimiento para obtener 7 para el nuevo min, luego devuelve el anterior min). Como cualquier valor que no causa un cambio, el mínimo actual es mayor que el mínimo actual, tiene algo que puede usarse para diferenciar entre los valores que cambian el mínimo y los que no lo hacen.

En los lenguajes que usan números enteros de tamaño fijo, está tomando prestado un poco de espacio de la representación de los valores, por lo que puede subdesbordarse y la aserción fallará. Pero de lo contrario, es un espacio extra constante y todas las operaciones siguen siendo O (1).

Las pilas que se basan en cambio en listas vinculadas tienen otros lugares de los que puede tomar prestado un poco, por ejemplo, en C el bit menos significativo del siguiente puntero, o en Java el tipo de objetos en la lista vinculada. Para Java, esto significa que se usa más espacio en comparación con una pila contigua, ya que tiene la sobrecarga del objeto por enlace:

public class LinkedStackWithMin {
    private static class Link {
        final int value;
        final Link next;

        Link ( int value, Link next ) {
            this.value = value;
            this.next = next;
        }

        int pop ( LinkedStackWithMin stack ) {
            stack.top = next;
            return value;
        }
    }

    private static class MinLink extends Link {
        MinLink ( int value, Link next ) {
            super( value, next );
        }

        int pop ( LinkedStackWithMin stack ) {
            stack.top = next;
            int prevMin = stack.min;
            stack.min = value;
            return prevMin;
        }
    }

    Link top;
    int min;

    public LinkedStackWithMin () {
    }

    public void push ( int val ) {
        if ( ( top == null ) || ( val < min ) ) {
            top = new MinLink(min, top);
            min = val;
        } else {
            top = new Link(val, top);
        }
    }

    public int pop () {
        return top.pop(this);
    }

    public int getMin () {
        return min;
    }

    public boolean isEmpty () {
        return top == null;
    }

En C, la sobrecarga no está ahí, y puede tomar prestado el lsb del siguiente puntero:

typedef struct _stack_link stack_with_min;

typedef struct _stack_link stack_link;

struct _stack_link {
    size_t  next;
    int     value;
};

stack_link* get_next ( stack_link* link ) 
{
    return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}

bool is_min ( stack_link* link )
{
    return ( link -> next & 1 ) ! = 0;
}

void push ( stack_with_min* stack, int value )
{
    stack_link *link = malloc ( sizeof( stack_link ) );

    link -> next = ( size_t ) stack -> next;

    if ( (stack -> next == 0) || ( value == stack -> value ) ) {
        link -> value = stack -> value;
        link -> next |= 1; // mark as min
    } else {
        link -> value = value;
    }

    stack -> next = link;
}

etc.;

Sin embargo, ninguno de estos es verdaderamente O (1). No requieren más espacio en la práctica, porque aprovechan los huecos en las representaciones de números, objetos o punteros en estos lenguajes. Pero una máquina teórica que usara una representación más compacta requeriría agregar un bit extra a esa representación en cada caso.

Encontré una solución que satisface todas las restricciones mencionadas (operaciones de tiempo constante) y espacio extra constante .

La idea es almacenar la diferencia entre el valor mínimo y el número de entrada, y actualizar el valor mínimo si ya no es el mínimo.

El código es el siguiente:

public class MinStack {
    long min;
    Stack<Long> stack;

    public MinStack(){
        stack = new Stack<>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = x;
        } else {
            stack.push(x - min); //Could be negative if min value needs to change
            if (x < min) min = x;
        }
    }

    public int pop() {
        if (stack.isEmpty()) return;

        long pop = stack.pop();

        if (pop < 0) {
            long ret = min
            min = min - pop; //If negative, increase the min value
            return (int)ret;
        }
        return (int)(pop + min);

    }

    public int top() {
        long top = stack.peek();
        if (top < 0) {
            return (int)min;
        } else {
           return (int)(top + min);
        }
    }

    public int getMin() {
        return (int)min;
    }
}

El crédito va a: https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack

Bueno, ¿cuáles son las limitaciones de tiempo de ejecución de pushy pop? Si no se requiere que sean constantes, simplemente calcule el valor mínimo en esas dos operaciones (haciéndolas O ( n )). De lo contrario, no veo cómo se puede hacer esto con espacio adicional constante.

Aquí está mi código que se ejecuta con O (1). El código anterior que publiqué tenía un problema cuando aparece el elemento mínimo. Modifiqué mi código. Este usa otra pila que mantiene el elemento mínimo presente en la pila por encima del elemento empujado actual.

 class StackDemo
{
    int[] stk = new int[100];
    int top;
    public StackDemo()
    {
        top = -1;
    }
    public void Push(int value)
    {
        if (top == 100)
            Console.WriteLine("Stack Overflow");
        else
            stk[++top] = value;
    }
    public bool IsEmpty()
    {
        if (top == -1)
            return true;
        else
            return false;
    }
    public int Pop()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Stack Underflow");
            return 0;
        }
        else
            return stk[top--];
    }
    public void Display()
    {
        for (int i = top; i >= 0; i--)
            Console.WriteLine(stk[i]);
    }
}
class MinStack : StackDemo
{
    int top;
    int[] stack = new int[100];
    StackDemo s1; int min;
    public MinStack()
    {
        top = -1;
        s1 = new StackDemo();
    }
    public void PushElement(int value)
    {
        s1.Push(value);
        if (top == 100)
            Console.WriteLine("Stack Overflow");
        if (top == -1)
        {
            stack[++top] = value;
            stack[++top] = value;   
        }
        else
        {
            //  stack[++top]=value;
            int ele = PopElement();
            stack[++top] = ele;
            int a = MininmumElement(min, value);
              stack[++top] = min;

                stack[++top] = value;
                stack[++top] = a;


        }
    }
    public int PopElement()
    {

        if (top == -1)
            return 1000;
        else
        {
            min = stack[top--];
            return stack[top--];
        }

    }
    public int PopfromStack()
    {
        if (top == -1)
            return 1000;
        else
        {
            s1.Pop();
            return PopElement();
        }
    }
    public int MininmumElement(int a,int b)
    {
        if (a > b)
            return b;
        else
            return a;
    }
    public int StackTop()
    {
        return stack[top];
    }
    public void DisplayMinStack()
    {
        for (int i = top; i >= 0; i--)
            Console.WriteLine(stack[i]);
    }
}
class Program
{
    static void Main(string[] args)
    {
        MinStack ms = new MinStack();
        ms.PushElement(15);
        ms.PushElement(2);
        ms.PushElement(1);
        ms.PushElement(13);
        ms.PushElement(5);
        ms.PushElement(21);
        Console.WriteLine("Min Stack");
        ms.DisplayMinStack();
        Console.WriteLine("Minimum Element:"+ms.StackTop());
        ms.PopfromStack();
        ms.PopfromStack();
        ms.PopfromStack();
        ms.PopfromStack();

        Console.WriteLine("Min Stack");
        ms.DisplayMinStack();
        Console.WriteLine("Minimum Element:" + ms.StackTop());
        Thread.Sleep(1000000);
    }
}

Usé un tipo diferente de pila. Aquí está la implementación.

//
//  main.cpp
//  Eighth
//
//  Created by chaitanya on 4/11/13.
//  Copyright (c) 2013 cbilgika. All rights reserved.
//

#include <iostream>
#include <limits>
using namespace std;
struct stack
{
    int num;
    int minnum;
}a[100];

void push(int n,int m,int &top)
{

    top++;
    if (top>=100) {
        cout<<"Stack Full";
        cout<<endl;
    }
    else{
        a[top].num = n;
        a[top].minnum = m;
    }


}

void pop(int &top)
{
    if (top<0) {
        cout<<"Stack Empty";
        cout<<endl;
    }
    else{
       top--; 
    }


}
void print(int &top)
{
    cout<<"Stack: "<<endl;
    for (int j = 0; j<=top ; j++) {
        cout<<"("<<a[j].num<<","<<a[j].minnum<<")"<<endl;
    }
}


void get_min(int &top)
{
    if (top < 0)
    {
        cout<<"Empty Stack";
    }
    else{
        cout<<"Minimum element is: "<<a[top].minnum;
    }
    cout<<endl;
}

int main()
{

    int top = -1,min = numeric_limits<int>::min(),num;
    cout<<"Enter the list to push (-1 to stop): ";
    cin>>num;
    while (num!=-1) {
        if (top == -1) {
            min = num;
            push(num, min, top);
        }
        else{
            if (num < min) {
                min = num;
            }
            push(num, min, top);
        }
        cin>>num;
    }
    print(top);
    get_min(top);
    return 0;
}

Salida:

Enter the list to push (-1 to stop): 5
1
4
6
2
-1
Stack: 
(5,5)
(1,1)
(4,1)
(6,1)
(2,1)
Minimum element is: 1

Intentalo. Creo que responde a la pregunta. El segundo elemento de cada par da el valor mínimo visto cuando se insertó ese elemento.

Estoy publicando el código completo aquí para encontrar el mínimo y el máximo en una pila determinada.

La complejidad del tiempo será O (1) ..

package com.java.util.collection.advance.datastructure;

/**
 * 
 * @author vsinha
 *
 */
public abstract interface Stack<E> {

    /**
     * Placing a data item on the top of the stack is called pushing it
     * @param element
     * 
     */
    public abstract void push(E element);


    /**
     * Removing it from the top of the stack is called popping it
     * @return the top element
     */
    public abstract E pop();

    /**
     * Get it top element from the stack and it 
     * but the item is not removed from the stack, which remains unchanged
     * @return the top element
     */
    public abstract E peek();

    /**
     * Get the current size of the stack.
     * @return
     */
    public abstract int size();


    /**
     * Check whether stack is empty of not.
     * @return true if stack is empty, false if stack is not empty
     */
    public abstract boolean empty();



}



package com.java.util.collection.advance.datastructure;

@SuppressWarnings("hiding")
public abstract interface MinMaxStack<Integer> extends Stack<Integer> {

    public abstract int min();

    public abstract int max();

}


package com.java.util.collection.advance.datastructure;

import java.util.Arrays;

/**
 * 
 * @author vsinha
 *
 * @param <E>
 */
public class MyStack<E> implements Stack<E> {

    private E[] elements =null;
    private int size = 0;
    private int top = -1;
    private final static int DEFAULT_INTIAL_CAPACITY = 10;


    public MyStack(){
        // If you don't specify the size of stack. By default, Stack size will be 10
        this(DEFAULT_INTIAL_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public MyStack(int intialCapacity){
        if(intialCapacity <=0){
            throw new IllegalArgumentException("initial capacity can't be negative or zero");
        }
        // Can't create generic type array
        elements =(E[]) new Object[intialCapacity];
    }

    @Override
    public void push(E element) {
        ensureCapacity();
        elements[++top] = element;
        ++size;
    }

    @Override
    public E pop() {
        E element = null;
        if(!empty()) {
            element=elements[top];
            // Nullify the reference
            elements[top] =null;
            --top;
            --size;
        }
        return element;
    }

    @Override
    public E peek() {
        E element = null;
        if(!empty()) {
            element=elements[top];
        }
        return element;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean empty() {
        return size == 0;
    }

    /**
     * Increases the capacity of this <tt>Stack by double of its current length</tt> instance, 
     * if stack is full 
     */
    private void ensureCapacity() {
        if(size != elements.length) {
            // Don't do anything. Stack has space.
        } else{
            elements = Arrays.copyOf(elements, size *2);
        }
    }

    @Override
    public String toString() {
        return "MyStack [elements=" + Arrays.toString(elements) + ", size="
                + size + ", top=" + top + "]";
    }


}


package com.java.util.collection.advance.datastructure;

/**
 * Time complexity will be O(1) to find min and max in a given stack.
 * @author vsinha
 *
 */
public class MinMaxStackFinder extends MyStack<Integer> implements MinMaxStack<Integer> {

    private MyStack<Integer> minStack;

    private MyStack<Integer> maxStack;

    public MinMaxStackFinder (int intialCapacity){
        super(intialCapacity);
        minStack =new MyStack<Integer>();
        maxStack =new MyStack<Integer>();

    }
    public void push(Integer element) {
        // Current element is lesser or equal than min() value, Push the current element in min stack also.
        if(!minStack.empty()) {
            if(min() >= element) {
                minStack.push(element);
            }
        } else{
            minStack.push(element);
        }
        // Current element is greater or equal than max() value, Push the current element in max stack also.
        if(!maxStack.empty()) {
            if(max() <= element) {
                maxStack.push(element);
            }
        } else{
            maxStack.push(element);
        }
        super.push(element);
    }


    public Integer pop(){
        Integer curr = super.pop();
        if(curr !=null) {
            if(min() == curr) {
                minStack.pop();
            } 

            if(max() == curr){
                maxStack.pop();
            }
        }
        return curr;
    }


    @Override
    public int min() {
        return minStack.peek();
    }

    @Override
    public int max() {
        return maxStack.peek();
    }


    @Override
    public String toString() {
        return super.toString()+"\nMinMaxStackFinder [minStack=" + minStack + "\n maxStack="
                + maxStack + "]" ;
    }




}

// You can use the below program to execute it.

package com.java.util.collection.advance.datastructure;

import java.util.Random;

public class MinMaxStackFinderApp {

    public static void main(String[] args) {
        MinMaxStack<Integer> stack =new MinMaxStackFinder(10);
        Random random =new Random();
        for(int i =0; i< 10; i++){
            stack.push(random.nextInt(100));
        }
        System.out.println(stack);
        System.out.println("MAX :"+stack.max());
        System.out.println("MIN :"+stack.min());

        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();

        System.out.println(stack);
        System.out.println("MAX :"+stack.max());
        System.out.println("MIN :"+stack.min());
    }
}

Avísame si tienes algún problema

Gracias, Vikash

Puede extender su clase de pila original y simplemente agregarle el seguimiento mínimo. Deje que la clase padre original maneje todo lo demás como de costumbre.

public class StackWithMin extends Stack<Integer> {  

    private Stack<Integer> min;

    public StackWithMin() {
        min = new Stack<>();
    }

    public void push(int num) {
        if (super.isEmpty()) {
            min.push(num);
        } else if (num <= min.peek()) {
            min.push(num);
        }
        super.push(num);
    }

    public int min() {
        return min.peek();
    }

    public Integer pop() {
        if (super.peek() == min.peek()) {
            min.pop();
        }
        return super.pop();
    }   
}

Aquí está mi solución en java usando la lista de me gusta.

class Stack{
    int min;
    Node top;
    static class Node{
        private int data;
        private Node next;
        private int min;

        Node(int data, int min){
           this.data = data;
           this.min = min;
           this.next = null; 
    }
}

  void push(int data){
        Node temp;
        if(top == null){
            temp = new Node(data,data);
            top = temp;
            top.min = data;
        }
        if(top.min > data){
            temp = new Node(data,data);
            temp.next = top;
            top = temp;
        } else {
            temp = new Node(data, top.min);
            temp.next = top;
            top = temp;
        }
  }

  void pop(){
    if(top != null){
        top = top.next;
    }
  }

  int min(){
    return top.min;
  }

}

Supongamos que la pila en la que trabajaremos es la siguiente:

6 , minvalue=2
2 , minvalue=2
5 , minvalue=3
3 , minvalue=3
9 , minvalue=7
7 , minvalue=7
8 , minvalue=8

En la representación anterior, la pila solo se construye con el valor de la izquierda, el [valor mínimo] del valor de la derecha se escribe solo con fines ilustrativos, que se almacenará en una variable.

El problema real es cuando el valor que es el valor mínimo obtenido se elimina en ese punto, ¿cómo podemos saber cuál es el siguiente elemento mínimo sin iterar sobre la pila?

Como, por ejemplo, en nuestra pila cuando aparecen 6 get, sabemos que este no es el elemento mínimo porque el elemento mínimo es 2, por lo que podemos eliminarlo de forma segura sin actualizar nuestro valor mínimo.

Pero cuando mostramos 2, podemos ver que el valor mínimo es 2 en este momento y si este mensaje aparece, entonces debemos actualizar el valor mínimo a 3.

Punto 1:

Ahora, si observa cuidadosamente, necesitamos generar minvalue = 3 a partir de este estado particular [2, minvalue = 2]. o si va a depper en la pila, necesitamos generar minvalue = 7 a partir de este estado particular [3, minvalue = 3] o si va más depper en la pila, entonces necesitamos generar minvalue = 8 a partir de este estado en particular [7, minvalue = 7]

¿Notó algo en común en los 3 casos anteriores? El valor que necesitamos generar depende de dos variables que son iguales. Correcto. ¿Por qué sucede esto? Porque cuando empujamos algún elemento más pequeño que el minvalue actual, básicamente empujamos ese elemento en la pila y también actualizamos el mismo número en minvalue.

Punto2:

Básicamente, estamos almacenando duplicados del mismo número una vez en la pila y una vez en la variable minvalue. Necesitamos enfocarnos en evitar esta duplicación y almacenar algo de datos útiles en la pila o el minvalue para generar el mínimo anterior como se muestra en CASOS arriba.

Centrémonos en lo que debemos almacenar en la pila cuando el valor para almacenar en push es menor que el valor mínimo. Vamos a nombrar esta variable y, por lo que ahora nuestra pila se verá así:

6 , minvalue=2
y1 , minvalue=2
5 , minvalue=3
y2 , minvalue=3
9 , minvalue=7
y3 , minvalue=7
8 , minvalue=8

Los he renombrado como y1, y2, y3 para evitar confusión de que todos tendrán el mismo valor.

Punto3:

Ahora intentemos encontrar algunas restricciones sobre y1, y2 e y3. ¿Recuerda cuándo exactamente necesitamos actualizar el minvalue mientras hacemos pop (), solo cuando hemos extraído el elemento que es igual al minvalue? Si sacamos algo mayor que el minvalue, entonces no tenemos que actualizar minvalue. Entonces, para activar la actualización de minvalue, y1, y2 & y3 deberían ser más pequeños que el minvalue correspondiente. [Estamos evitando la igualdad para evitar duplicar [Point2]] por lo que la restricción es [y <minValue].

Ahora volvamos a rellenar y, necesitamos generar algún valor y poner y en el momento de empujar, recuerda. Tomemos el valor que viene para empujar como x, que es menor que prevMinvalue, y el valor que realmente empujaremos en la pila es y. Así que una cosa es obvia que newMinValue = x, y y <newMinvalue.

Ahora necesitamos calcular y (recuerde que y puede ser cualquier número que sea menor que newMinValue (x) así que necesitamos encontrar algún número que pueda cumplir con nuestra restricción) con la ayuda de prevMinvalue yx (newMinvalue).

Let's do the math:
    x < prevMinvalue [Given]
    x - prevMinvalue < 0 
    x - prevMinValue + x < 0 + x [Add x on both side]
    2*x - prevMinValue < x      
this is the y which we were looking for less than x(newMinValue).
y = 2*x - prevMinValue. 'or' y = 2*newMinValue - prevMinValue 'or' y = 2*curMinValue - prevMinValue [taking curMinValue=newMinValue].

Entonces, en el momento de presionar x si es menor que prevMinvalue, presionamos y [2 * x-prevMinValue] y actualizamos newMinValue = x.

Y en el momento del estallido, si la pila contiene algo menos que minValue, ese es nuestro disparador para actualizar minVAlue. Tenemos que calcular prevMinValue a partir de curMinValue e y. y = 2 * curMinValue - prevMinValue [probado] prevMinVAlue = 2 * curMinvalue - y.

2 * curMinValue - y es el número que necesitamos actualizar ahora al prevMinValue.

El código para la misma lógica se comparte a continuación con la complejidad de O (1) tiempo y O (1) espacio.

// C++ program to implement a stack that supports 
// getMinimum() in O(1) time and O(1) extra space. 
#include <bits/stdc++.h> 
using namespace std; 

// A user defined stack that supports getMin() in 
// addition to push() and pop() 
struct MyStack 
{ 
    stack<int> s; 
    int minEle; 

    // Prints minimum element of MyStack 
    void getMin() 
    { 
        if (s.empty()) 
            cout << "Stack is empty\n"; 

        // variable minEle stores the minimum element 
        // in the stack. 
        else
            cout <<"Minimum Element in the stack is: "
                 << minEle << "\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 < minEle means minEle stores 
        // value of t. 
        (t < minEle)? cout << minEle: 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(); 

        // Minimum will change as the minimum element 
        // of the stack is being removed. 
        if (t < minEle) 
        { 
            cout << minEle << "\n"; 
            minEle = 2*minEle - t; 
        } 

        else
            cout << t << "\n"; 
    } 

    // Removes top element from MyStack 
    void push(int x) 
    { 
        // Insert new number into the stack 
        if (s.empty()) 
        { 
            minEle = x; 
            s.push(x); 
            cout <<  "Number Inserted: " << x << "\n"; 
            return; 
        } 

        // If new number is less than minEle 
        if (x < minEle) 
        { 
            s.push(2*x - minEle); 
            minEle = x; 
        } 

        else
           s.push(x); 

        cout <<  "Number Inserted: " << x << "\n"; 
    } 
}; 

// Driver Code 
int main() 
{ 
    MyStack s; 
    s.push(3); 
    s.push(5); 
    s.getMin(); 
    s.push(2); 
    s.push(1); 
    s.getMin(); 
    s.pop(); 
    s.getMin(); 
    s.pop(); 
    s.peek(); 

    return 0; 
} 

Aquí está mi versión de implementación.

 struct MyStack {
    elemento int;
    int * CurrentMiniAddress;
 };

 empuje vacío (valor int)
 {
    // Crea tu estructura y completa el valor
    MyStack S = new MyStack ();
    S-> elemento = valor;

    si (Stack.Empty ())
    {    
        // Como la pila está vacía, apunte CurrentMiniAddress a sí mismo
        S-> CurrentMiniAddress = S;

    }
    más
    {
         // La pila no está vacía

         // Recupera el elemento superior. Sin pop ()
         MyStack * TopElement = Stack.Top ();

         // Recuerde siempre que el elemento TOP apunta al
         // elemento mínimo en toda la pila
         if (S-> elemento CurrentMiniAddress-> elemento)
         {
            // Si el valor actual es el mínimo en toda la pila
            // entonces S se apunta a sí mismo
            S-> CurrentMiniAddress = S;
         }
             más
             {
                 // Entonces este no es el mínimo en toda la pila
                 // No se preocupe, TOP tiene el elemento mínimo
                 S-> CurrentMiniAddress = TopElement-> CurrentMiniAddress;
             }

    }
        Apilar.Añadir (S);
 }

 pop vacío ()
 {
     si (! Stack.Empty ())
     {
        Stack.Pop ();
     }  
 }

 int GetMinimum (apilar y apilar)
 {
       si (! pila.Empty ())
       {
            MyStack * Top = stack.top ();
            // Top siempre apunta al mínimo x
            return Top-> CurrentMiniAddress-> elemento;
        }
 }

#include<stdio.h>
struct stack
{
    int data;
    int mindata;
}a[100];

void push(int *tos,int input)
{
    if (*tos > 100)
    {
        printf("overflow");
        return;
    }
    (*tos)++;
    a[(*tos)].data=input;
    if (0 == *tos)
        a[*tos].mindata=input;
    else if (a[*tos -1].mindata < input)
        a[*tos].mindata=a[*tos -1].mindata;
    else
        a[*tos].mindata=input;
}

int pop(int * tos)
{
    if (*tos <= -1)
    {
        printf("underflow");
        return -1;
    }
    return(a[(*tos)--].data);
}
void display(int tos)
{
    while (tos > -1)
    {
        printf("%d:%d\t",a[tos].data,a[tos].mindata);
        tos--;
    }    
}

int min(int tos)
{
   return(a[tos].mindata);
}
int main()
{
int tos=-1,x,choice;
while(1)
{
    printf("press 1-push,2-pop,3-mindata,4-display,5-exit ");
    scanf("%d",&choice);
    switch(choice)
    {
    case 1: printf("enter data to push");
            scanf("%d",&x);
            push(&tos,x);
            break;
    case 2: printf("the poped out data=%d ",pop(&tos));
            break;
    case 3: printf("The min peeped data:%d",min(tos));
            break;
    case 4: printf("The elements of stack \n");
            display(tos);
            break;
    default: exit(0);
}
}

Encontré esta solución aquí

struct StackGetMin {
  void push(int x) {
    elements.push(x);
    if (minStack.empty() || x <= minStack.top())
      minStack.push(x);
  }
  bool pop() {
    if (elements.empty()) return false;
    if (elements.top() == minStack.top())
      minStack.pop();
    elements.pop();
    return true;
  }
  bool getMin(int &min) {
    if (minStack.empty()) {
      return false;
    } else {
      min = minStack.top();
      return true;
    }
  }
  stack<int> elements;
  stack<int> minStack;
};

struct Node {
    let data: Int
    init(_ d:Int){
        data = d
    }
}

struct Stack {
    private var backingStore = [Node]()
    private var minArray = [Int]()

    mutating func push(n:Node) {
        backingStore.append(n)
        minArray.append(n.data)
        minArray.sort(>)
        minArray
    }

    mutating func pop() -> Node? {
        if(backingStore.isEmpty){
            return nil
        }

        let n = backingStore.removeLast()

        var found = false
        minArray = minArray.filter{
            if (!found && $0 == n.data) {
                found = true
                return false
            }
            return true
        }
        return n
    }

    func min() -> Int? {
        return minArray.last
    }
}

 class MyStackImplementation{
private final int capacity = 4;
int min;
int arr[] = new int[capacity];
int top = -1;

public void push ( int val ) {
top++;
if(top <= capacity-1){
    if(top == 0){
min = val;
arr[top] = val;
}
else if(val < min){
arr[top] = arr[top]+min;
min = arr[top]-min;
arr[top] = arr[top]-min;
}
else {
arr[top] = val;
}
System.out.println("element is pushed");
}
else System.out.println("stack is full");

}

 public void pop () {
top--;
   if(top > -1){ 

   min = arr[top];
}
else {min=0; System.out.println("stack is under flow");}

}
public int min(){
return min;
}

 public boolean isEmpty () {
    return top == 0;
}

public static void main(String...s){
MyStackImplementation msi = new MyStackImplementation();
msi.push(1);
msi.push(4);
msi.push(2);
msi.push(10);
System.out.println(msi.min);
msi.pop();
msi.pop();
msi.pop();
msi.pop();
msi.pop();
System.out.println(msi.min);

}
}

class FastStack {

    private static class StackNode {
        private Integer data;
        private StackNode nextMin;

        public StackNode(Integer data) {
            this.data = data;
        }

        public Integer getData() {
            return data;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public StackNode getNextMin() {
            return nextMin;
        }

        public void setNextMin(StackNode nextMin) {
            this.nextMin = nextMin;
        }

    }

    private LinkedList<StackNode> stack = new LinkedList<>();

    private StackNode currentMin = null;

    public void push(Integer item) {
        StackNode node = new StackNode(item);
        if (currentMin == null) {
            currentMin = node;
            node.setNextMin(null);
        } else if (item < currentMin.getData()) {
            StackNode oldMinNode = currentMin;
            node.setNextMin(oldMinNode);
            currentMin = node;
        }

        stack.addFirst(node);
    }

    public Integer pop() {
        if (stack.isEmpty()) {
            throw new EmptyStackException();
        }
        StackNode node = stack.peek();
        if (currentMin == node) {
            currentMin = node.getNextMin();
        }
        stack.removeFirst();
        return node.getData();
    }

    public Integer getMinimum() {
        if (stack.isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        return currentMin.getData();
    }
}

Aquí está mi código que se ejecuta con O (1). Aquí utilicé un par de vectores que contiene el valor que empujó y también contiene el valor mínimo hasta este valor empujado.

Aquí está mi versión de la implementación de C ++.

vector<pair<int,int> >A;
int sz=0; // to keep track of the size of vector

class MinStack
{
public:
    MinStack()
    {
        A.clear();
        sz=0;
    }

    void push(int x)
    {
        int mn=(sz==0)?x: min(A[sz-1].second,x); //find the minimum value upto this pushed value
        A.push_back(make_pair(x,mn));
        sz++; // increment the size
    }

    void pop()
    {
        if(sz==0) return;
        A.pop_back(); // pop the last inserted element
        sz--;  // decrement size
    }

    int top()
    {
        if(sz==0)   return -1;  // if stack empty return -1
        return A[sz-1].first;  // return the top element
    }

    int getMin()
    {
        if(sz==0) return -1;
        return A[sz-1].second; // return the minimum value at sz-1 
    }
};

    **The task can be acheived by creating two stacks:**



import java.util.Stack;
    /*
     * 
     * Find min in stack using O(n) Space Complexity
     */
    public class DeleteMinFromStack {

        void createStack(Stack<Integer> primary, Stack<Integer> minStack, int[] arr) {
    /* Create main Stack and in parallel create the stack which contains the minimum seen so far while creating main Stack */
            primary.push(arr[0]);
            minStack.push(arr[0]);

            for (int i = 1; i < arr.length; i++) {
                primary.push(arr[i]);
                if (arr[i] <= minStack.peek())// Condition to check to push the value in minimum stack only when this urrent value is less than value seen at top of this stack */
                    minStack.push(arr[i]);
            }

        }

        int findMin(Stack<Integer> secStack) {
            return secStack.peek();
        }

        public static void main(String args[]) {

            Stack<Integer> primaryStack = new Stack<Integer>();
            Stack<Integer> minStack = new Stack<Integer>();

            DeleteMinFromStack deleteMinFromStack = new DeleteMinFromStack();

            int[] arr = { 5, 5, 6, 8, 13, 1, 11, 6, 12 };
            deleteMinFromStack.createStack(primaryStack, minStack, arr);
            int mimElement = deleteMinFromStack.findMin(primaryStack, minStack);
    /** This check for algorithm when the main Stack Shrinks by size say i as in loop below */
            for (int i = 0; i < 2; i++) {
                primaryStack.pop();
            }

            System.out.println(" Minimum element is " + mimElement);
        }

    }
/*
here in have tried to add for loop wherin the main tack can be shrinked/expaned so we can check the algorithm */

Una implementación práctica para encontrar el mínimo en una pila de objetos diseñados por el usuario, denominada: Escuela

La pila va a almacenar las escuelas en la pila según el rango asignado a una escuela en una región específica, digamos, findMin () le da a la escuela donde obtenemos el número máximo de solicitudes de admisión, que a su vez se definirá por el comparador que utiliza el rango asociado con las escuelas en la temporada anterior.

The Code for same is below:


   package com.practical;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class CognitaStack {

    public School findMin(Stack<School> stack, Stack<School> minStack) {

        if (!stack.empty() && !minStack.isEmpty())
            return (School) minStack.peek();
        return null;
    }

    public School removeSchool(Stack<School> stack, Stack<School> minStack) {

        if (stack.isEmpty())
            return null;
        School temp = stack.peek();
        if (temp != null) {
            // if(temp.compare(stack.peek(), minStack.peek())<0){
            stack.pop();
            minStack.pop();
            // }

            // stack.pop();
        }
        return stack.peek();
    }

    public static void main(String args[]) {

        Stack<School> stack = new Stack<School>();
        Stack<School> minStack = new Stack<School>();

        List<School> lst = new LinkedList<School>();

        School s1 = new School("Polam School", "London", 3);
        School s2 = new School("AKELEY WOOD SENIOR SCHOOL", "BUCKINGHAM", 4);
        School s3 = new School("QUINTON HOUSE SCHOOL", "NORTHAMPTON", 2);
        School s4 = new School("OAKLEIGH HOUSE SCHOOL", " SWANSEA", 5);
        School s5 = new School("OAKLEIGH-OAK HIGH SCHOOL", "Devon", 1);
        School s6 = new School("BritishInter2", "Devon", 7);

        lst.add(s1);
        lst.add(s2);
        lst.add(s3);
        lst.add(s4);
        lst.add(s5);
        lst.add(s6);

        Iterator<School> itr = lst.iterator();
        while (itr.hasNext()) {
            School temp = itr.next();
            if ((minStack.isEmpty()) || (temp.compare(temp, minStack.peek()) < 0)) { // minStack.peek().equals(temp)
                stack.push(temp);
                minStack.push(temp);
            } else {
                minStack.push(minStack.peek());
                stack.push(temp);
            }

        }

        CognitaStack cogStack = new CognitaStack();
        System.out.println(" Minimum in Stack is " + cogStack.findMin(stack, minStack).name);
        cogStack.removeSchool(stack, minStack);
        cogStack.removeSchool(stack, minStack);

        System.out.println(" Minimum in Stack is "
                + ((cogStack.findMin(stack, minStack) != null) ? cogStack.findMin(stack, minStack).name : "Empty"));
    }

}

Además, el objeto de la escuela es el siguiente:

package com.practical;

import java.util.Comparator;

public class School implements Comparator<School> {

    String name;
    String location;
    int rank;

    public School(String name, String location, int rank) {
        super();
        this.name = name;
        this.location = location;
        this.rank = rank;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((location == null) ? 0 : location.hashCode());
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + rank;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        School other = (School) obj;
        if (location == null) {
            if (other.location != null)
                return false;
        } else if (!location.equals(other.location))
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        if (rank != other.rank)
            return false;
        return true;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getLocation() {
        return location;
    }

    public void setLocation(String location) {
        this.location = location;
    }

    public int getRank() {
        return rank;
    }

    public void setRank(int rank) {
        this.rank = rank;
    }

    public int compare(School o1, School o2) {
        // TODO Auto-generated method stub
        return o1.rank - o2.rank;
    }

}

class SchoolComparator implements Comparator<School> {

    public int compare(School o1, School o2) {
        return o1.rank - o2.rank;
    }

}

Este ejemplo cubre lo siguiente: 1. Implementación de Stack para objetos definidos por el usuario, aquí, School 2. Implementación para el método hashcode () y equals () usando todos los campos de Objetos a comparar 3. Una implementación práctica para el escenario donde rqeuire para que la operación Stack contains esté en el orden de O (1)

Aquí está la implementación de PHP de lo que se explica en la respuesta de Jon Skeet como la implementación de complejidad de espacio ligeramente mejor para obtener el máximo de pila en O (1).

<?php

/**
 * An ordinary stack implementation.
 *
 * In real life we could just extend the built-in "SplStack" class.
 */
class BaseIntegerStack
{
    /**
     * Stack main storage.
     *
     * @var array
     */
    private $storage = [];

    // ------------------------------------------------------------------------
    // Public API
    // ------------------------------------------------------------------------

    /**
     * Pushes to stack.
     *
     * @param  int $value New item.
     *
     * @return bool
     */
    public function push($value)
    {
        return is_integer($value)
            ? (bool) array_push($this->storage, $value)
            : false;
    }

    /**
     * Pops an element off the stack.
     *
     * @return int
     */
    public function pop()
    {
        return array_pop($this->storage);
    }

    /**
     * See what's on top of the stack.
     *
     * @return int|bool
     */
    public function top()
    {
        return empty($this->storage)
            ? false
            : end($this->storage);
    }

    // ------------------------------------------------------------------------
    // Magic methods
    // ------------------------------------------------------------------------

    /**
     * String representation of the stack.
     *
     * @return string
     */
    public function __toString()
    {
        return implode('|', $this->storage);
    }
} // End of BaseIntegerStack class

/**
 * The stack implementation with getMax() method in O(1).
 */
class Stack extends BaseIntegerStack
{
    /**
     * Internal stack to keep track of main stack max values.
     *
     * @var BaseIntegerStack
     */
    private $maxStack;

    /**
     * Stack class constructor.
     *
     * Dependencies are injected.
     *
     * @param BaseIntegerStack $stack Internal stack.
     *
     * @return void
     */
    public function __construct(BaseIntegerStack $stack)
    {
        $this->maxStack = $stack;
    }

    // ------------------------------------------------------------------------
    // Public API
    // ------------------------------------------------------------------------

    /**
     * Prepends an item into the stack maintaining max values.
     *
     * @param  int $value New item to push to the stack.
     *
     * @return bool
     */
    public function push($value)
    {
        if ($this->isNewMax($value)) {
            $this->maxStack->push($value);
        }

        parent::push($value);
    }

    /**
     * Pops an element off the stack maintaining max values.
     *
     * @return int
     */
    public function pop()
    {
        $popped = parent::pop();

        if ($popped == $this->maxStack->top()) {
            $this->maxStack->pop();
        }

        return $popped;
    }

    /**
     * Finds the maximum of stack in O(1).
     *
     * @return int
     * @see push()
     */
    public function getMax()
    {
        return $this->maxStack->top();
    }

    // ------------------------------------------------------------------------
    // Internal helpers
    // ------------------------------------------------------------------------

    /**
     * Checks that passing value is a new stack max or not.
     *
     * @param  int $new New integer to check.
     *
     * @return boolean
     */
    private function isNewMax($new)
    {
        return empty($this->maxStack) OR $new > $this->maxStack->top();
    }

} // End of Stack class

// ------------------------------------------------------------------------
// Stack Consumption and Test
// ------------------------------------------------------------------------
$stack = new Stack(
    new BaseIntegerStack
);

$stack->push(9);
$stack->push(4);
$stack->push(237);
$stack->push(5);
$stack->push(556);
$stack->push(15);

print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n\n";

print "Pop: {$stack->pop()}\n";
print "Pop: {$stack->pop()}\n\n";

print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n\n";

print "Pop: {$stack->pop()}\n";
print "Pop: {$stack->pop()}\n\n";

print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n";

// Here's the sample output:
//
// Stack: 9|4|237|5|556|15
// Max: 556
//
// Pop: 15
// Pop: 556
//
// Stack: 9|4|237|5
// Max: 237
//
// Pop: 5
// Pop: 237
//
// Stack: 9|4
// Max: 9

Aquí está la implementación de C ++ de Jon Skeets Answer . Puede que no sea la forma más óptima de implementarlo, pero hace exactamente lo que se supone que debe hacer.

class Stack {
private:
    struct stack_node {
        int val;
        stack_node *next;
    };
    stack_node *top;
    stack_node *min_top;
public:
    Stack() {
        top = nullptr;
        min_top = nullptr;
    }    
    void push(int num) {
        stack_node *new_node = nullptr;
        new_node = new stack_node;
        new_node->val = num;

        if (is_empty()) {
            top = new_node;
            new_node->next = nullptr;

            min_top = new_node;
            new_node->next = nullptr;
        } else {
            new_node->next = top;
            top = new_node;

            if (new_node->val <= min_top->val) {
                new_node->next = min_top;
                min_top = new_node;
            }
        }
    }

    void pop(int &num) {
        stack_node *tmp_node = nullptr;
        stack_node *min_tmp = nullptr;

        if (is_empty()) {
            std::cout << "It's empty\n";
        } else {
            num = top->val;
            if (top->val == min_top->val) {
                min_tmp = min_top->next;
                delete min_top;
                min_top = min_tmp;
            }
            tmp_node = top->next;
            delete top;
            top = tmp_node;
        }
    }

    bool is_empty() const {
        return !top;
    }

    void get_min(int &item) {
        item = min_top->val;
    }
};

Y aquí está el conductor de la clase.

int main() {
    int pop, min_el;
    Stack my_stack;

    my_stack.push(4);
    my_stack.push(6);
    my_stack.push(88);
    my_stack.push(1);
    my_stack.push(234);
    my_stack.push(2);

    my_stack.get_min(min_el);
    cout << "Min: " << min_el << endl;

    my_stack.pop(pop);
    cout << "Popped stock element: " << pop << endl;

    my_stack.pop(pop);
    cout << "Popped stock element: " << pop << endl;

    my_stack.pop(pop);
    cout << "Popped stock element: " << pop << endl;

    my_stack.get_min(min_el);
    cout << "Min: " << min_el << endl;

    return 0;
}

Salida:

Min: 1
Popped stock element: 2
Popped stock element: 234
Popped stock element: 1
Min: 4

Nosotros podemos hacer esto en un tiempo O (n) y O (1) la complejidad del espacio, así:

class MinStackOptimized:
  def __init__(self):
      self.stack = []
      self.min = None

  def push(self, x): 
      if not self.stack:
          # stack is empty therefore directly add
          self.stack.append(x)
          self.min = x 
      else:
          """
          Directly add (x-self.min) to the stack. This also ensures anytime we have a 
          negative number on the stack is when x was less than existing minimum
          recorded thus far.
          """
          self.stack.append(x-self.min)
          if x < self.min:
              # Update x to new min
              self.min = x 

  def pop(self):
      x = self.stack.pop()
      if x < 0:
          """ 
          if popped element was negative therefore this was the minimum
          element, whose actual value is in self.min but stored value is what
          contributes to get the next min. (this is one of the trick we use to ensure
          we are able to get old minimum once current minimum gets popped proof is given
          below in pop method), value stored during push was:
          (x - self.old_min) and self.min = x therefore we need to backtrack
          these steps self.min(current) - stack_value(x) actually implies to
              x (self.min) - (x - self.old_min)
          which therefore gives old_min back and therefore can now be set
          back as current self.min.
          """
          self.min = self.min - x 

  def top(self):
      x = self.stack[-1]
      if x < 0:
          """ 
          As discussed above anytime there is a negative value on stack, this
          is the min value so far and therefore actual value is in self.min,
          current stack value is just for getting the next min at the time
          this gets popped.
          """
          return self.min
      else:
          """ 
          if top element of the stack was positive then it's simple, it was
          not the minimum at the time of pushing it and therefore what we did
          was x(actual) - self.min(min element at current stage) let's say `y`
          therefore we just need to reverse the process to get the actual
          value. Therefore self.min + y, which would translate to
              self.min + x(actual) - self.min, thereby giving x(actual) back
          as desired.
          """
          return x + self.min

  def getMin(self):
      # Always self.min variable holds the minimum so for so easy peezy.
      return self.min

Creo que simplemente puede usar una LinkedList en la implementación de su pila.

La primera vez que inserta un valor, coloca este valor como el encabezado de la lista vinculada.

luego, cada vez que presiona un valor, si el nuevo valor <head.data, realice una operación de envío previo (lo que significa que el cabezal se convierte en el nuevo valor)

si no es así, realice una operación de adición.

Cuando hace un pop (), comprueba si min == linkedlist.head.data, si es así, entonces head = head.next;

Aquí está mi código.

public class Stack {

int[] elements;
int top;
Linkedlists min;

public Stack(int n) {
    elements = new int[n];
    top = 0;
    min = new Linkedlists();
}

public void realloc(int n) {
    int[] tab = new int[n];
    for (int i = 0; i < top; i++) {
        tab[i] = elements[i];
    }

    elements = tab;
}

public void push(int x) {
    if (top == elements.length) {
        realloc(elements.length * 2);
    }
    if (top == 0) {
        min.pre(x);
    } else if (x < min.head.data) {
        min.pre(x);
    } else {
        min.app(x);
    }
    elements[top++] = x;
}

public int pop() {

    int x = elements[--top];
    if (top == 0) {

    }
    if (this.getMin() == x) {
        min.head = min.head.next;
    }
    elements[top] = 0;
    if (4 * top < elements.length) {
        realloc((elements.length + 1) / 2);
    }

    return x;
}

public void display() {
    for (Object x : elements) {
        System.out.print(x + " ");
    }

}

public int getMin() {
    if (top == 0) {
        return 0;
    }
    return this.min.head.data;
}

public static void main(String[] args) {
    Stack stack = new Stack(4);
    stack.push(2);
    stack.push(3);
    stack.push(1);
    stack.push(4);
    stack.push(5);
    stack.pop();
    stack.pop();
    stack.pop();
    stack.push(1);
    stack.pop();
    stack.pop();
    stack.pop();
    stack.push(2);
    System.out.println(stack.getMin());
    stack.display();

}

 }

public class MinStack<E>{

    private final LinkedList<E> mainStack = new LinkedList<E>();
    private final LinkedList<E> minStack = new LinkedList<E>();
    private final Comparator<E> comparator;

    public MinStack(Comparator<E> comparator) 
    {
        this.comparator = comparator;
    }

    /**
     * Pushes an element onto the stack.
     *
     *
     * @param e the element to push
     */
    public void push(E e) {
        mainStack.push(e);
        if(minStack.isEmpty())
        {
            minStack.push(e);
        }
        else if(comparator.compare(e, minStack.peek())<=0)
        {
            minStack.push(e);
        }
        else
        {
            minStack.push(minStack.peek());
        }
    }

    /**
     * Pops an element from the stack.
     *
     *
     * @throws NoSuchElementException if this stack is empty
     */
    public E pop() {
       minStack.pop();
       return  mainStack.pop();
    }

    /**
     * Returns but not remove smallest element from the stack. Return null if stack is empty.
     *
     */
    public E getMinimum()
    {
        return minStack.peek();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Main stack{");
        for (E e : mainStack) {         
            sb.append(e.toString()).append(",");
        }
        sb.append("}");

        sb.append(" Min stack{");
        for (E e : minStack) {          
            sb.append(e.toString()).append(",");
        }
        sb.append("}");

        sb.append(" Minimum = ").append(getMinimum());
        return sb.toString();
    }

    public static void main(String[] args) {
        MinStack<Integer> st = new MinStack<Integer>(Comparators.INTEGERS);

        st.push(2);
        Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
        System.out.println(st);

        st.push(6);
        Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
        System.out.println(st);

        st.push(4);
        Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
        System.out.println(st);

        st.push(1);
        Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
        System.out.println(st);

        st.push(5);
        Assert.assertTrue("1 is min in stack {2,6,4,1,5}", st.getMinimum().equals(1));
        System.out.println(st);

        st.pop();
        Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
        System.out.println(st);

        st.pop();
        Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
        System.out.println(st);

        st.pop();
        Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
        System.out.println(st);

        st.pop();
        Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
        System.out.println(st);

        st.pop();
        Assert.assertTrue("null is min in stack {}", st.getMinimum()==null);
        System.out.println(st);
    }
}

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Solution 
{
    public class MinStack
    {
        public MinStack()
        {
            MainStack=new Stack<int>();
            Min=new Stack<int>();
        }

        static Stack<int> MainStack;
        static Stack<int> Min;

        public void Push(int item)
        {
            MainStack.Push(item);

            if(Min.Count==0 || item<Min.Peek())
                Min.Push(item);
        }

        public void Pop()
        {
            if(Min.Peek()==MainStack.Peek())
                Min.Pop();
            MainStack.Pop();
        }
        public int Peek()
        {
            return MainStack.Peek();
        }

        public int GetMin()
        {
            if(Min.Count==0)
                throw new System.InvalidOperationException("Stack Empty"); 
            return Min.Peek();
        }
    }
}

Vi una solución brillante aquí: https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

A continuación se muestra el código de Python que escribí siguiendo el algoritmo:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class MinStack:
    def __init__(self):
        self.head = None
        self.min = float('inf')

    # @param x, an integer
    def push(self, x):
        if self.head == None:
            self.head = Node(x)
            self.min = x
        else:
            if x >= self.min:
                n = Node(x)
                n.next = self.head
                self.head = n
            else:
                v = 2 * x - self.min
                n = Node(v)
                n.next = self.head
                self.head = n
                self.min = x

    # @return nothing
    def pop(self):
        if self.head:
            if self.head.value < self.min:
                self.min = self.min * 2 - self.head.value
            self.head = self.head.next

    # @return an integer
    def top(self):
        if self.head:
            if self.head.value < self.min:
                self.min = self.min * 2 - self.head.value
                return self.min
            else:
                return self.head.value
        else:
            return -1

    # @return an integer
    def getMin(self):
        if self.head:
            return self.min
        else:
            return -1

Para obtener elementos mínimos de Stack. Tenemos que usar Two stack .ie Stack s1 y Stack s2.

1. Inicialmente, ambas pilas están vacías, así que agregue elementos a ambas pilas

--------------------- Llame recursivamente del Paso 2 al 4 -----------------------

2. si se agregó un nuevo elemento a la pila s1.Entonces, saque los elementos de la pila s2

3. compare los nuevos elementos con s2. cuál es más pequeño, empuje a s2.

4. pop de la pila s2 (que contiene el elemento min)

El código se ve así:

package Stack;
import java.util.Stack;
public class  getMin 
{  

        Stack<Integer> s1= new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();

        void push(int x)
        {
            if(s1.isEmpty() || s2.isEmpty())

            {
                 s1.push(x);
                 s2.push(x);
            }
            else
            {

               s1. push(x);
                int y = (Integer) s2.pop();
                s2.push(y);
                if(x < y)
                    s2.push(x);
                        }
        }
        public Integer pop()
        {
            int x;
            x=(Integer) s1.pop();
            s2.pop();
            return x;

        }
    public  int getmin()
        {
            int x1;
            x1= (Integer)s2.pop();
            s2.push(x1);
            return x1;
        }

    public static void main(String[] args) {
        getMin s = new getMin();
            s.push(10);
            s.push(20);
            s.push(30);
            System.out.println(s.getmin());
            s.push(1);
            System.out.println(s.getmin());
        }

}

Creo que solo la operación de empuje sufre, es suficiente. Mi implementación incluye una pila de nodos. Cada nodo contiene el elemento de datos y también el mínimo en ese momento. Este mínimo se actualiza cada vez que se realiza una operación de inserción.

Aquí hay algunos puntos para comprender:

• Implementé la pila usando Linked List.

• La parte superior de un puntero siempre apunta al último elemento empujado. Cuando no hay ningún elemento en esa pila, la parte superior es NULL.

• Cuando se inserta un elemento, se asigna un nuevo nodo que tiene un puntero siguiente que apunta a la pila anterior y la parte superior se actualiza para apuntar a este nuevo nodo.

La única diferencia con la implementación de pila normal es que durante la inserción se actualiza un miembro mínimo para el nuevo nodo.

Eche un vistazo al código que se implementa en C ++ con fines de demostración.

/*
 *  Implementation of Stack that can give minimum in O(1) time all the time
 *  This solution uses same data structure for minimum variable, it could be implemented using pointers but that will be more space consuming
 */

#include <iostream>
using namespace std;

typedef struct stackLLNodeType stackLLNode;

struct stackLLNodeType {
    int item;
    int min;
    stackLLNode *next;
};

class DynamicStack {
private:
    int stackSize;
    stackLLNode *top;

public:
    DynamicStack();
    ~DynamicStack();
    void push(int x);
    int pop();
    int getMin();
    int size() { return stackSize; }
};

void pushOperation(DynamicStack& p_stackObj, int item);
void popOperation(DynamicStack& p_stackObj);

int main () {
    DynamicStack stackObj;

    pushOperation(stackObj, 3);
    pushOperation(stackObj, 1);
    pushOperation(stackObj, 2);
    popOperation(stackObj);
    popOperation(stackObj);
    popOperation(stackObj);
    popOperation(stackObj);
    pushOperation(stackObj, 4);
    pushOperation(stackObj, 7);
    pushOperation(stackObj, 6);
    popOperation(stackObj);
    popOperation(stackObj);
    popOperation(stackObj);
    popOperation(stackObj);

    return 0;
}

DynamicStack::DynamicStack() {
    // initialization
    stackSize = 0;
    top = NULL;
}

DynamicStack::~DynamicStack() {
    stackLLNode* tmp;
    // chain memory deallocation to avoid memory leak
    while (top) {
        tmp = top;
        top = top->next;
        delete tmp;
    }
}

void DynamicStack::push(int x) {
    // allocate memory for new node assign to top
    if (top==NULL) {
        top = new stackLLNode;
        top->item = x;
        top->next = NULL;
        top->min = top->item;
    }
    else {
        // allocation of memory
        stackLLNode *tmp = new stackLLNode;
        // assign the new item
        tmp->item = x;
        tmp->next = top;

        // store the minimum so that it does not get lost after pop operation of later minimum
        if (x < top->min)
            tmp->min = x;
        else
            tmp->min = top->min;

        // update top to new node
        top = tmp;
    }
    stackSize++;
}

int DynamicStack::pop() {
    // check if stack is empty
    if (top == NULL)
        return -1;

    stackLLNode* tmp = top;
    int curItem = top->item;
    top = top->next;
    delete tmp;
    stackSize--;
    return curItem;
}

int DynamicStack::getMin() {
    if (top == NULL)
        return -1;
    return top->min;
}
void pushOperation(DynamicStack& p_stackObj, int item) {
    cout<<"Just pushed: "<<item<<endl;
    p_stackObj.push(item);
    cout<<"Current stack min: "<<p_stackObj.getMin()<<endl;
    cout<<"Current stack size: "<<p_stackObj.size()<<endl<<endl;
}

void popOperation(DynamicStack& p_stackObj) {
    int popItem = -1;
    if ((popItem = p_stackObj.pop()) == -1 )
        cout<<"Cannot pop. Stack is empty."<<endl;
    else {
        cout<<"Just popped: "<<popItem<<endl;
        if (p_stackObj.getMin() == -1)
            cout<<"No minimum. Stack is empty."<<endl;
        else
            cout<<"Current stack min: "<<p_stackObj.getMin()<<endl;
        cout<<"Current stack size: "<<p_stackObj.size()<<endl<<endl;
    }
}

Y la salida del programa se ve así:

Just pushed: 3
Current stack min: 3
Current stack size: 1

Just pushed: 1
Current stack min: 1
Current stack size: 2

Just pushed: 2
Current stack min: 1
Current stack size: 3

Just popped: 2
Current stack min: 1
Current stack size: 2

Just popped: 1
Current stack min: 3
Current stack size: 1

Just popped: 3
No minimum. Stack is empty.
Current stack size: 0

Cannot pop. Stack is empty.
Just pushed: 4
Current stack min: 4
Current stack size: 1

Just pushed: 7
Current stack min: 4
Current stack size: 2

Just pushed: 6
Current stack min: 4
Current stack size: 3

Just popped: 6
Current stack min: 4
Current stack size: 2

Just popped: 7
Current stack min: 4
Current stack size: 1

Just popped: 4
No minimum. Stack is empty.
Current stack size: 0

Cannot pop. Stack is empty.

public interface IMinStack<T extends Comparable<T>> {
  public void push(T val);
  public T pop();
  public T minValue();
  public int size();
}

import java.util.Stack;

public class MinStack<T extends Comparable<T>> implements IMinStack<T> {
  private Stack<T> stack = new Stack<T>();
  private Stack<T> minStack = new Stack<T>();

  @Override
  public void push(T val) {
    stack.push(val);
    if (minStack.isEmpty() || val.compareTo(minStack.peek()) < 0)
        minStack.push(val);
  }

  @Override
  public T pop() {
    T val = stack.pop();
    if ((false == minStack.isEmpty())
            && val.compareTo(minStack.peek()) == 0)
        minStack.pop();
    return val;
  }

  @Override
  public T minValue() {
    return minStack.peek();
  }

  @Override
  public int size() {
    return stack.size();
  }
}