155. Min Stack
## description
## 155. Min Stack
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(int 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.
You must implement a solution with O(1) time complexity for each function.
Example 1:
1Input
2["MinStack","push","push","push","getMin","pop","top","getMin"]
3[[],[-2],[0],[-3],[],[],[],[]]
4
5Output
6[null,null,null,null,-3,null,0,-2]
7
8Explanation
9MinStack minStack = new MinStack();
10minStack.push(-2);
11minStack.push(0);
12minStack.push(-3);
13minStack.getMin(); // return -3
14minStack.pop();
15minStack.top(); // return 0
16minStack.getMin(); // return -2- –-231 <= val <= 231 - 1
- –Methods pop, top and getMin operations will always be called on non-empty stacks.
- –At most 3 * 104 calls will be made to push, pop, top, and getMin.
Constraints:
## notes
### Intuition
To support O(1) minimum retrieval, we need to track minimums as they change. A second stack that only stores values when they become the new minimum (or equal to it) maintains this information.
### Implementation
Maintain two stacks: the main stack and a min stack. On push, always add to the main stack; if the value is less than or equal to the current minimum (or min stack is empty), also push to min stack. On pop, if the popped value equals the min stack top, pop from min stack too. getMin returns the top of min stack. top returns the main stack top.
### Edge-cases
Push to min stack when value equals the current min (not just less than) to handle duplicate minimums correctly.
- –Time: O(1) — all operations are constant time
- –Space: O(n) — both stacks can grow to n elements
### Complexity
## solution
1class MinStack:
2
3 def __init__(self):
4 self.min_stack = []
5 self.stack = []
6
7
8 def push(self, val: int) -> None:
9 self.stack.append(val)
10
11 if val <= self.getMin() or not self.min_stack:
12 self.min_stack.append(val)
13
14
15 def pop(self) -> None:
16 if self.min_stack and self.min_stack[-1] == self.stack[-1]:
17 self.min_stack.pop()
18 self.stack.pop()
19
20
21 def top(self) -> int:
22 return self.stack[-1] # will always be called on non-empty stack
23
24
25 def getMin(self) -> int:
26 if self.min_stack:
27 return self.min_stack[-1]
28 return self.top()
29
30
31
32# Your MinStack object will be instantiated and called as such:
33# obj = MinStack()
34# obj.push(val)
35# obj.pop()
36# param_3 = obj.top()
37# param_4 = obj.getMin()
38
39
40
41if __name__ == "__main__":
42 # Include one-off tests here or debugging logic that can be run by running this file
43 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
44 obj = MinStack()
45