最小栈

古城微笑少年丶 2022-02-25 00:28 213阅读 0赞

**题目描述**

设计一个支持 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.

**解法**  
思路1：时间换空间法，不使用多余空间  
代码如下：

class MinStack {
    		
    		private ArrayList<Integer> list;
    		
    		private int min = Integer.MAX_VALUE;
    		
    	    /** initialize your data structure here. */
    	    public MinStack() {
    	    	list = new ArrayList<Integer>();
    	    }
    	    
    	    public void push(int x) {
    	    	if(x < min) {
    	    		min = x;
    	    	}
    	        list.add(x);
    	    }
    	    
    	    public void pop() {
    	    	int size = list.size();
    	    	if(size == 0) {
    	    		return;
    	    	}
    	        int top = list.get(size -1);
    	        if(top == min) {
    	        	int newMin = Integer.MAX_VALUE;
    	        	for(int i=0;i<size-1;i++) {
    	        		if(list.get(i)<newMin) {
    	        			newMin = list.get(i);
    	        		}
    	        	}
    	        	min = newMin;
    	        }
    	        list.remove(size -1);
    	    }
    	    
    	    public int top() {
    	    	int size = list.size();
    	    	if(size == 0) {
    	    		throw new RuntimeException();
    	    	}
    	        return list.get(size -1);
    	    }
    	    
    	    public int getMin() {
    	        return min;
    	    }
    	}

思路2：空间换时间法，使用额外存储，降低操作时间

/**
    * 每次push两个值，1：元素，2：当前栈的最小值
    * 空间换时间
    * @param x
    */
    class MinStack {
    		
    		private Stack<Integer> stack;
    		
    	    /** initialize your data structure here. */
    	    public MinStack() {
    	    	stack = new Stack<Integer>();
    	    }
    	    
    	    public void push(int x) {
    	    	if(stack.isEmpty()) {
    	    		stack.add(x);
    	    		stack.add(x);
    	    	}else {
    	    		int min = stack.peek();
                    stack.add(x);
    	    		stack.add(x<min?x:min);
    			}
    	    }
    	    
    	    public void pop() {
    	    	stack.pop();
    	    	stack.pop();
    	    }
    	    
    	    public int top() {
    	    	return stack.get(stack.size()-2);
    	    }
    	    
    	    public int getMin() {
    	        return stack.peek();
    	    }
    	}