MinStack

Last updated Mar 26, 2023 Edit Source

# Notas

MinStack es un problema que busca que crees tu propia stack en la cual las operaciones sean de O(1) todas. Cuatro operaciones principales.

push. Agregar un elemento al tope de la pila
pop. Remover el elemento al tope de la pila
top. Traer el elemento al tope de la pila
min. Traer el elemento minimo de la pila.

Para implementarlo existen dos caminos viables, el facil que es utilizando la estructura Stack que ya se incluye en la libreria estandar de los lenguajes. La otra es utilizar arrays y punteros para mantener en track el indice del ultimo elemento agregado.

Yo personalmente me decante por esta ultima, por tanto, mantuve dos arrays, uno para los datos y otro para los valores minimos en dado momento, adicionalmente, un puntero para mantener en track el ultimo indice y una variable para guardar el valor minimo en dado momento.

# Solucion

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class MinStack {

    private int latestElementIndex;
    private int[] elements;
    private int[] mins;
    private int minTracker;
  
    public MinStack() {
        this.elements = new int[30000];
        this.mins = new int[30000];
        this.latestElementIndex = -1;
        this.minTracker = Integer.MAX_VALUE;
    }

    public void push(int val) {
        latestElementIndex++;
        if (val < minTracker) {
            minTracker = val;
            this.mins[latestElementIndex] = val;
        } else {
            this.mins[latestElementIndex] = minTracker;
        }
        elements[latestElementIndex] = val;
    }

    public void pop() {
        mins[latestElementIndex] = 0;
        elements[latestElementIndex] = 0;
        latestElementIndex--;
        if (latestElementIndex < 0) {
            minTracker = Integer.MAX_VALUE;
        } else {
            minTracker = mins[latestElementIndex];
        }
    }

    public int top() {
        if (latestElementIndex < 0) {
            return 0;
        }
        return elements[latestElementIndex];
    }

    public int getMin() {
        if (latestElementIndex < 0) {
            return 0;
        }
        return mins[latestElementIndex];
    }
}

🌱 Digital Garden

MinStack

# Notas

# Solucion

Backlinks

Interactive Graph