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:
- MinStack() initializes the stack object.
- void push(val) pushes the element val onto the stack.
- void pop() removes the element on the top of the stack.
- int top() gets the top element of the stack.
- int getMin() retrieves the minimum element in the stack.
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); }
0 Comments