Min Stack or Max Stack
Four cases
We have two interesting problems in leetcode, one is min stack and one is max stack. Actually, it is not the min or max to make the difference. It is whether we have the pop_max or pop_min operation make the difference.
We have four combinations:
- a) Min Stack without popmin
- b) Max Stack without popmax
- c) Min Stack with popmin
- d) Max stack with popmax
The first two are very similar to each other. And the last two are very similar to each other. From the Leetcode, the Min Stack problem means case a) and the Max Stack problem means case d)
Min stack (case a)
155. Min Stack
Code
For this code, all operations are in O(1).
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self._stack = []
self._min_values = []
def push(self, x: int) -> None:
self._stack.append(x)
if not self._min_values:
self._min_values.append(x)
else:
self._min_values.append(min(self._min_values[-1], x))
def pop(self) -> None:
if self._stack:
self._stack.pop()
self._min_values.pop()
def top(self) -> int:
return self._stack[-1] if self._stack else -1
def getMin(self) -> int:
return self._min_values[-1] if self._min_values else float('inf')
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()Max stack (case d)
Solution 1: A naive O(n) peekmax and O(n) popmax code. (204 ms)
class MaxStack:
def __init__(self):
"""
initialize your data structure here.
"""
self._stack = []
def push(self, x: int) -> None:
self._stack.append(x)
def pop(self) -> int:
return self._stack.pop()
def top(self) -> int:
if self._stack:
return self._stack[-1]
return -1
def peekMax(self) -> int:
if self._stack:return max(self._stack)
return- float('inf')
def popMax(self) -> int:
max_, idx = -float('inf'), 0
if not self._stack:return max_
for i, a in enumerate(self._stack):
if a>=max_:
max_, idx = a, i
self._stack.pop(idx)
return max_
# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()Solution 2: Two stacks to have an O(1) peekMax and O(n) popMax (192 ms)
Two stacks by borrowing the idea from the here. TK(Another problem was using a similar strategy. Should be using a stack to mimic queue or using a queue to mimic stack? Will figure it our late)
“A regular stack already supports the first 3 operations, so we focus on the last two.
For peekMax, we remember the largest value we've seen on the side. For example, if we add, we'll remember [2, 2, 5, 5, 9]. This works seamlessly with pop operations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.
For popMax, we know what the current maximum (peekMax) is. We can pop until we find that maximum, then push the popped elements back on the stack.
Our implementation in Python will showcase extending the list class.”
A naive implementation fails in this case:
[“MaxStack”,”push”,”push”,”popMax”,”peekMax”]
[[],[5],[1],[],[]]
As after we popMax, the self._max_values will contain the wrong information.
It is supposed to change from [5,5] to [1], however, the code below will change [5,5] to [5]. The reason is if we delete the maximum number 5, it will not only have an influence on the last one but also to the first one.
class MaxStack:
def __init__(self):
"""
initialize your data structure here.
"""
self._stack = []
self._max_values = []
def push(self, x: int) -> None:
self._stack.append(x)
if not self._max_values:self._max_values.append(x)
else:
self._max_values.append(max(x, self._max_values[-1]))
print('self._max', self._max_values)
def pop(self) -> int:
self._max_values.pop()
return self._stack.pop()
def top(self) -> int:
if self._stack:
return self._stack[-1]
return -1
def peekMax(self) -> int:
if self._stack:return self._max_values[-1]
return -float('inf')
def popMax(self) -> int:
if not self._max_values:return -float('inf')
max_ = self._max_values.pop()
stack2 = []
while True:
stack2.append(self._stack.pop())
if stack2[-1]==max_:
# find the max and pop the max
stack2.pop()
while stack2:
self._stack.append(stack2.pop())
break
return max_
# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()Improved code
Using self.pop and self.push to maintain the consistency of the self._stack and self._max_values
class MaxStack:
def __init__(self):
self._stack = []
self._max_values =[]
def push(self, x):
self._stack.append(x)
if not self._max_values:self._max_values.append(x)
else:
this_max = max(x, self._max_values[-1])
self._max_values.append(this_max)
def top(self):
return self._stack[-1]
def pop(self):
#print('pop ',self._stack)
self._max_values.pop()
return self._stack.pop()
def peekMax(self):
return self._max_values[-1]
def popMax(self):
if not self._max_values:return -float('inf')
max_ = self._max_values[-1]
stack2 = []
while self._stack[-1]!=max_:
stack2.append(self.pop())
self.pop()
while stack2:
self.push(stack2.pop())
return max_Solution 3: (140 ms)
An excellent post from here
import heapq
class MaxStack:
def __init__(self):
self.soft_deleted = set()
self.max_heap = []
self.recency_stack = []
self.next_id = 0
def push(self, x: int) -> None:
heapq.heappush(self.max_heap, (-x, self.next_id))
self.recency_stack.append((x, self.next_id))
self.next_id -= 1
def _clean_up(self):
while self.recency_stack and self.recency_stack[-1][1] in self.soft_deleted:
self.soft_deleted.remove(self.recency_stack.pop()[1])
while self.max_heap and self.max_heap[0][1] in self.soft_deleted:
self.soft_deleted.remove(heapq.heappop(self.max_heap)[1])
def pop(self) -> int:
entry_to_return = self.recency_stack.pop()
self.soft_deleted.add(entry_to_return[1])
self._clean_up()
return entry_to_return[0]
def top(self) -> int:
return self.recency_stack[-1][0]
def peekMax(self) -> int:
return -self.max_heap[0][0]
def popMax(self) -> int:
value, time = heapq.heappop(self.max_heap)
self.soft_deleted.add(time)
self._clean_up()
return value * -1The above solution from here by Heidi Newton is really nice. I change the self.recency_stack and change the update the self.next_id from subtracting by 1 to increasing by 1. And I’d like to demonstrate the whole process of the algorithm.
Example A: put(4), put(3), put(2), put(1), pop(), popmax(), pop(max)
Example B: put(1), put(2), put(3), put(4), pop(), popmax(), pop(max)
Example A process
Example B process
Conclusion about the complexity of the above algorithm (solution 3)
Example A: put(4), put(3), put(2), put(1), pop(), popmax(), pop(max)
Example B: put(1), put(2), put(3), put(4), pop(), popmax(), pop(max)
I built those examples on purpose to see what is the complexity in the best case and worst case. From the process, we can see:
if the data is putting into the stack by a reverse sorted order, we will have the best case as both the two while loops in _clean_up function is not needed.
Specifically in the best case (such as for example A):
- push(): O(log n) (heappush operation);
- pop(): O(1)
- top(): O(1)
- popmax(): O(log n) (heappop operation)
in the worst case (such as for example B):
- push(): O(log n) (heappush operation);
- pop(): O(log n) (heappop operation)
- top(): O(1)
- popmax(): O(log n) (heappop operation)
Another implementation
class MaxStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.hq = []
self.t = 0
self.deleted = set()
def push(self, x: int) -> None:
self.stack.append((x, self.t))
heapq.heappush(self.hq, (-x, -self.t))
self.t += 1
def pop(self) -> int:
if not self.stack:return -1
top, t = self.stack.pop()
self.deleted.add(t)
self._clean_up()
return top
def top(self) -> int:
if not self.stack:return -1
return self.stack[-1][0]
def _clean_up(self):
while self.hq and -self.hq[0][1] in self.deleted:
heapq.heappop(self.hq)
while self.stack and self.stack[-1][1] in self.deleted:
self.stack.pop()
def peekMax(self) -> int:
return -self.hq[0][0] if self.hq else -1
def popMax(self) -> int:
if not self.hq:return -1
x, t = heapq.heappop(self.hq)
self.deleted.add(-t)
self._clean_up()
return -x
# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()C++ implementation
typedef pair<int, int> ii;
class MaxStack {
private:
stack<ii> st;
priority_queue<ii> pq;
unordered_set<int> toBeDel;
int time = 0;
void cleanup() {
while (!pq.empty() && toBeDel.count(pq.top().second)) {
pq.pop();
}
while (!st.empty() && toBeDel.count(st.top().second)) {
st.pop();
}
}
public:
/** initialize your data structure here. */
MaxStack() {
}
void push(int x) {
st.emplace(x, time);
pq.emplace(x, time);
time++;
}
int pop() {
if(st.empty()) return -1;
auto [val, thisTime] = st.top();
toBeDel.insert(st.top().second);
st.pop();
cleanup();
return val;
}
int top() {
return st.empty()? -1 : st.top().first;
}
int peekMax() {
return pq.empty()? -1 : pq.top().first;
}
int popMax() {
if (pq.empty()) return -1;
toBeDel.insert(pq.top().second);
auto max_ = pq.top().first;
pq.pop();
cleanup();
return max_;
}
};
/**
* Your MaxStack object will be instantiated and called as such:
* MaxStack* obj = new MaxStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->peekMax();
* int param_5 = obj->popMax();
*/Comparison of those 3 solutions
+--------+------------+---------------+---------------------+
| soluton| 1: naive | 2: two stack | 3: Heidi Newton |
+--------+------------+---------------+---------------------+
| push | O(1) | O(1) |O(log n) |
| pop | O(1) | O(1) |O(log n) |
| top | O(1) | O(1) |O(1) |
| peekmax| O(n) | O(1) |O(1) |
| popmax | O(n) | O(n) |O(log n) |
+------------+--------------------+-------------------------+Can we design operations in O(1) like the min stack problem?
No. A pretty good answer from here is:
“Because if it were, you could use this data structure to sort an array of numbers in O(n) time.
So, at the very least, either push(x) or popMax() must be O(logn)”
