Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Similar Problems:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) — Push element x onto stack.
- pop() — Removes the element on top of the stack.
- top() — Get the top element.
- getMin() — Retrieve the minimum element in the stack.
Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
Github: code.dennyzhang.com
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
## Blog link: https://code.dennyzhang.com/min-stack ## Basic Ideas: List with elements of (value, min_value) ## -2 0 -3 4 ## linked list: ## (-2, -2), (0, -2), (-3, -3), (4, -3) ## ## length: element count ## Complexity: Time: O(1), Space: O(n) class MinStack(object): def __init__(self): """ initialize your data structure here. """ self.length = 0 self.min_value = None self.values = [] def push(self, x): """ :type x: int :rtype: void """ if self.length == 0: element = (x, x) self.min_value = x else: if x > self.min_value: element = (x, self.min_value) else: self.min_value = x element = (x, x) self.values.append(element) self.length += 1 def pop(self): """ :rtype: void """ if self.length == 0: return if self.length == 1: self.min_value = None else: (x, previous_min_value) = self.values[-2] self.min_value = previous_min_value self.values.pop() self.length -= 1 def top(self): """ :rtype: int """ if len(self.values) == 0: return None else: (x, _min_value) = self.values[-1] return x def getMin(self): """ :rtype: int """ return self.min_value
Share It, If You Like It.