Min Stack
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.
4个函数都是O(1),运行时间是Java里较快的。
class MinStack {
class Node{
int val;
Node next;
Node pre;
Node last;// pointers to next minimun Node
Node(int x){
val = x;
next = null;
pre = null;
last = null;
}
}
Node head = new Node(0);
Node tail = head;
Node min = null;
public void push(int x) {
Node node = new Node(x);
// set stack
tail.next = node;
node.pre = tail;
tail = node;
// set min
if(min==null){
min = node;
}else{
if(node.val < min.val){
node.last = min;
min = node;
}else{
node.last = min;
}
}
}
public void pop() {
if(tail==head){
return;
}else{
min = tail.last;
tail = tail.pre;
}
}
public int top() {
return tail.val;
}
public int getMin() {
return min==null?0:min.val;
}
}
Improved Way: Solution里说的是用两个stack,一个正常存放,一个存min,每次push之前先看看是否min和当前被push元素相等,是就同时也push 出min。这样的做法也挺好的。
class MinStack {
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> min = new Stack<Integer>();
public void push(int x) {
if(min.isEmpty() || (!min.isEmpty() && x <= min.peek()))
min.push(x);
stack.push(x);
}
public void pop() {
if(!stack.isEmpty()&& !min.isEmpty()){
if((int)stack.peek()==(int)min.peek())
min.pop();
stack.pop();
}
}
public int top() {
return stack.isEmpty()?0:stack.peek();
}
public int getMin() {
return min.isEmpty()?0:min.peek();
}
}
还有一个很有创意的想法是用一个stack,遇到比当前min还小的就Push一次原来的min,pop的时候遇到min时就把当前min变成stack的下一个数,然后push掉这个记号。总体就是利用原stack存当前min。来自leetcode用户
class MinStack {
int min=Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
public void push(int x) {
// only push the old minimum value when the current
// minimum value changes after pushing the new value x
if(x <= min){
stack.push(min);
min=x;
}
stack.push(x);
}
public void pop() {
// if pop operation could result in the changing of the current minimum value,
// pop twice and change the current minimum value to the last minimum value.
if(stack.peek()==min) {
stack.pop();
min=stack.peek();
stack.pop();
}else{
stack.pop();
}
if(stack.empty()){
min=Integer.MAX_VALUE;
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
No comments:
Post a Comment