LeetCode-Min Stack(包含min函数的栈)

迷南。 2022-08-06 15:20 145阅读 0赞

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

问题的关键是getMin的时间复杂度是常量。最朴素的想法就是如下：

class MinStack {
        LinkedList<Integer> stack = new LinkedList<>();
    	Integer min = Integer.MAX_VALUE;
    	public void push(int x) {
    		stack.push(x);
    		if (x < min) {
    			min = x;
    		}
        }
    
        public void pop() {
        	stack.pop();
        	min = Integer.MAX_VALUE;
        	for (Integer index : stack) {
        		if (index < min) {
        			min = index;
        		}
        	}
        }
    
        public int top() {
        	return stack.peek();
        }
    
        public int getMin() {
        	return min;
        }
    }

每次在push和pop的时候求出最大值，很显然，pop的过程比较复杂，需要遍历整个栈，直接就超时。之后灵机一动，每次在push的时候，在搞一个栈把当前的最小值也push进去，如下代码：

LinkedList<Integer> stack = new LinkedList<Integer>();
    	LinkedList<Integer> minStack = new LinkedList<Integer>();
    	int min = Integer.MAX_VALUE;
        public void push(int x) {
        	stack.push(x);
        	 	minStack.push(min);
        }
    
        public void pop() {
        	stack.pop();
        	minStack.pop();
        }
    
        public int top() {
        	return stack.peek();
        }
    
        public int getMin() {
        	return minStack.peek();
        }

结果直接内存爆掉，可想而知，每次push，都会同时push最小值，相当于栈的空间是以前的两倍。但是可以做下优化，并不是push的时候push两次，而是在最小值发生变化的时候在push。这样会节省不少空间。上代码

class MinStack {
        LinkedList<Integer> stack = new LinkedList<Integer>();
    	LinkedList<Integer> minStack = new LinkedList<Integer>();
    	int min = Integer.MAX_VALUE;
        public void push(int x) {
        	stack.push(x);
        	if (min >= x) {
        		min = x;
        		minStack.push(min);
        	}
        }
    
        public void pop() {
        	if (min == stack.peek()) {
        		minStack.pop();
        		if (minStack.isEmpty()) {
        			min = Integer.MAX_VALUE;
        		} else {
        			min = minStack.peek();
        		}
        	}
        	stack.pop();
        }
    
        public int top() {
        	return stack.peek();
        }
    
        public int getMin() {
        	return min;
        }
    }

终于AC了！但是问题可以进一步探究，为什么存储的时候，不是把栈的差值存储呢？上代码：

LinkedList<Long> stack = new LinkedList<>();
    	long min = Integer.MAX_VALUE;
        public void push(int x) {
        	if (stack.isEmpty()) {
        		stack.push(0L);
        		min = x;
        	} else {
        		stack.push(x-min);
        		if (x < min) {
        			min = x;
        		}
        	}
        }
    
        public void pop() {
        	long pop = stack.pop();
        	if (pop < 0) {
        		min -= pop;
        	}
        }
    
        public int top() {
        	long top = stack.peek();
        	if (top > 0) {
        		return (int) (top+min);
        	} else {
        		return (int) min;
        	}
        }
    
        public int getMin() {
        	return (int) min;
        }

运行效率最好的方法！！！