LeetCode-Min Stack

浅浅的花香味﹌ 2022-08-04 00:38 56阅读 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.

一个比较经典的题了，为了在constant time内取得最小值，显然就是空间换时间了。最费空间的办法，也是最好想的办法就是。两个栈stack1, stack2。stack1存element，stack2存min。也就是在每次push(x)的时候，同时比较最小值push到stack2。很明显这个太浪费空间了，会报 [Memory Limit Exceeded][]错误。

所以就需要节省空间，不是每次push的时候都push最小值，而是每次最小值发生改变的时候才push。代码如下：

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

但是很有一个更狠的方法，只用一个栈就可以搞定，见下：

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

每次并不是push原数据，而是与min坐过差值之后在存放，good idea！！！

[Memory Limit Exceeded]: https://leetcode.com/submissions/detail/20390538/