leetcode.最小栈问题-白红宇

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。

pop() -- 删除栈顶的元素。

top() -- 获取栈顶元素。

getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();   --> 返回 -3.minStack.pop();minStack.top();      --> 返回 0.minStack.getMin();   --> 返回 -2.复制代码

刚看到题目。。自己第一个想法是要不要开一个链表慢慢比较栈中数据的大小。。后来百度一下，看到了正确思路。

首先开两个栈，一个栈a（放元素x），一个栈b（放最小值）。每当有元素x进栈时，元素x先跟栈b的栈顶比较，如果元素x比栈顶元素小，元素x入栈a、b；如果元素x大于栈顶元素，元素x入栈a。出栈时，出栈元素跟栈b的栈顶比较，如果出栈元素与栈b栈顶相等，栈b.pop()。这种方法能够避免，如果当前栈的最小值出栈时，就无法找到栈的最小值。

代码实现：

链表实现：

class MinStack {    private List
    
      data;    private List
     
       min;    /** initialize your data structure here. */    public MinStack() {        data = new ArrayList<>();        min = new ArrayList<>();    }        public void push(int x) {        if(data.isEmpty() || x <= min.get(min.size()-1)) {            min.add(x);        }        data.add(x);    }        public void pop() {        if(data.get(data.size()-1).equals(min.get(min.size()-1))){            min.remove(min.size()-1);        }        data.remove(data.size()-1);    }        public int top() {        return data.get(data.size()-1);    }        public int getMin() {        return min.get(min.size()-1);    }}复制代码

栈实现：

class MinStack {    private Stack
    
      data;    private Stack
     
       min;    /** initialize your data structure here. */    public MinStack() {        data = new Stack();        min = new Stack();    }        public void push(int x) {        if(data.isEmpty() || x <= min.peek()) {            min.push(x);        }        data.push(x);    }        public void pop() {        if(data.peek().equals(min.peek())){            min.pop();        }        data.pop();    }        public int top() {        return data.peek();    }        public int getMin() {        return min.peek();    }}复制代码