In this Leetcode Min Stack problem solution, we need to Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  1. MinStack() initializes the stack object.
  2. void push(val) pushes the element val onto the stack.
  3. void pop() removes the element on the top of the stack.
  4. int top() gets the top element of the stack.
  5. int getMin() retrieves the minimum element in the stack.

Leetcode Min Stack problem solution


Problem solution in Python.

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.p = []
        self.m = 9999999999999
    def push(self, x: int) -> None:
        self.p.append(x)
        self.m=min(self.m,x)
    def pop(self) -> None:
        tem=self.p.pop()
        if tem==self.m:
            if self.p:
                self.m=min(self.p)
            else:
                self.m=9999999999999
    def top(self) -> int:
        return self.p[-1]

    def getMin(self) -> int:
        if self.p:
            return self.m
        else:
            return None



Problem solution in Java.

Stack<Integer> stack;
int min ;
public MinStack() {
    min = Integer.MAX_VALUE;
    stack = new Stack<>();
}

public void push(int x) {
    if(x <= min){
        stack.push(min);
        min =x;
    }
    stack.push(x);
}
public void pop() {
    int x = stack.pop();
    if(x == min){
        min = stack.pop();
    }
}

public int top() {
    return stack.peek();
}

public int getMin() {
    return min;
}


Problem solution in C++.

class MinStack {
private:
    stack<int> activeStack;
    stack<int> minStack;
public:
    MinStack(): activeStack(), minStack() {}

    void push(int x) {
        activeStack.push(x);
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }

    void pop() {
        if (activeStack.top() == minStack.top()) {
            minStack.pop();
        }
        activeStack.pop();
    }

    int top() {  return activeStack.top(); }
    int getMin() { return minStack.top(); }
};


Problem solution in C.

typedef struct {
	int ele;
	int cur_min;
} Unit;

typedef struct {
	int max;
	int cur;
	Unit *pdata;
} MinStack;

void minStackCreate(MinStack *stack, int maxSize) {
	stack->max=maxSize;
	stack->cur=0;
	stack->pdata=malloc(sizeof(Unit)*maxSize);
}

void minStackPush(MinStack *stack, int element) {
	int c=stack->cur;
	if(c==stack->max)
		return;
	Unit *pd=stack->pdata;
	pd[c].ele=element;
	if(0<c){
		int last_min=pd[c-1].cur_min;
		if(element < pd[last_min].ele){
			pd[c].cur_min=c;
		}else{
			pd[c].cur_min=last_min;
		}
	}else{
		pd[0].cur_min=0;
	}
	++(stack->cur);
}

void minStackPop(MinStack *stack) {
	if(stack->cur>0){
		--(stack->cur);
	}
}

int minStackTop(MinStack *stack) {
	int c=stack->cur;
	if(c>0){
		return stack->pdata[c-1].ele;
	}else{
		return 0;
	}
}

int minStackGetMin(MinStack *stack) {
	int c=stack->cur;
	if(c>0){
		int min=stack->pdata[c-1].cur_min;
		return stack->pdata[min].ele;
	}else{
		return 0;
	}
}

void minStackDestroy(MinStack *stack) {
	stack->max=0;
	stack->cur=0;
	if(0!=stack->pdata)
		free(stack->pdata);
}