100 lines
3.0 KiB
Markdown
100 lines
3.0 KiB
Markdown
# 3.2. Stack Min
|
|
|
|
> Design a stack which has a function min, returning the minimum element. Push, pop and min should all operate in O(1) time.
|
|
|
|
## First idea
|
|
|
|
If it's supposed to be O(1) like `pop`, then just get another variable `min` in the class. But min must be updated every time a `pop` or `push` happens! I could have another function `update` to update the `min` but that's basically an appendix to `pop` and `push` so it doesn't work. If the new item to be `push`ed is lower than `min`, just update it. But what about `pop`? Then I'd have to do O(n). Either we do O(n) in time, or O(n) in space and have a stack of ordered values.
|
|
|
|
```java
|
|
public class MyStack<T> {
|
|
private static class StackNode<T> {
|
|
// attributes of nodes in the stack
|
|
private T data;
|
|
private StackNode<T> next;
|
|
|
|
public StackNode(T data){
|
|
this.data = data;
|
|
}
|
|
}
|
|
|
|
// attribute of the stack
|
|
private StackNode<T> top;
|
|
private StackNode<T> min;
|
|
min.data = 999;
|
|
|
|
public T pop() {
|
|
if (top == null){
|
|
throw new EmptyStackException();
|
|
}
|
|
T item = top.data;
|
|
top = top.next;
|
|
return item;
|
|
}
|
|
|
|
public void push(T item) {
|
|
StackNode<T> t = new StackNode<T>(item);
|
|
if (item < min) {
|
|
min = item;
|
|
}
|
|
t.next = top;
|
|
top = t;
|
|
}
|
|
}
|
|
```
|
|
|
|
## Hints
|
|
|
|
1. The min element doesn't change very often. Only changes when a smaller elem is added or the smallest elem is popped
|
|
2. What about storing extra data at each node? what sort of data might it be?
|
|
1. The next bigger element? That's O(n) space like before.
|
|
3. Consider having each node know the minimum of its "substack" (all the elements beneath it, including itself).
|
|
|
|
```java
|
|
public class MyStack<T> {
|
|
private static class StackNode<T> {
|
|
// attributes of nodes in the stack
|
|
private T data;
|
|
private StackNode<T> next;
|
|
private T min;
|
|
|
|
public StackNode(T data){
|
|
this.data = data;
|
|
}
|
|
}
|
|
|
|
// attribute of the stack
|
|
private StackNode<T> top;
|
|
|
|
public T pop() {
|
|
if (top == null){
|
|
throw new EmptyStackException();
|
|
}
|
|
T item = top.data;
|
|
top = top.next;
|
|
return item;
|
|
}
|
|
|
|
public void push(T item) {
|
|
StackNode<T> t = new StackNode<T>(item);
|
|
// first addition to stack or smaller numbers
|
|
if (top == null || item < top.min) {
|
|
t.min = item;
|
|
}
|
|
t.next = top;
|
|
top = t;
|
|
}
|
|
|
|
public void get_min() {
|
|
if (top == null){
|
|
throw new EmptyStackException();
|
|
}
|
|
return top.min;
|
|
}
|
|
}
|
|
```
|
|
|
|
## Solution
|
|
|
|
Having just an integer works well except when the minimum element is popped, then it takes O(n) to update the stack. But for larger stacks, it takes a lot of space. We could create a stack of mins. [Code for solution](https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2003.%20Stacks%20and%20Queues/Q3_02_Stack_Min).
|