最小栈问题

最小栈的问题

首先明确定义：什么是最小栈？就是栈中有一个getMin（）方法可以常数复杂度的获取栈中的最小值，所以暴力遍历栈获取最小值是十分不明智的，所以我们会采用一个辅助栈，来帮助我们获取最小值。通常有两种方案，和主栈同步，和主栈不同步。

---

和主栈同步：就是指主栈和辅助栈一定会增加元素

import java.util.Stack;

public class MinStack {

    // 数据栈
    private Stack<Integer> data;
    // 辅助栈
    private Stack<Integer> helper;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        data = new Stack<>();
        helper = new Stack<>();
    }

    // 思路 1：数据栈和辅助栈在任何时候都同步

    public void push(int x) {
        // 数据栈和辅助栈一定会增加元素
        data.add(x);
        if (helper.isEmpty() || helper.peek() >= x) {
            helper.add(x);
        } else {
            helper.add(helper.peek());
        }
    }

    public void pop() {
        // 两个栈都得 pop
        if (!data.isEmpty()) {
            helper.pop();
            data.pop();
        }
    }

    public int top() {
        if(!data.isEmpty()){
            return data.peek();
        }
        throw new RuntimeException("栈中元素为空，此操作非法");
    }

    public int getMin() {
        if(!helper.isEmpty()){
            return helper.peek();
        }
        throw new RuntimeException("栈中元素为空，此操作非法");
    }
}

和主栈不同步：在辅助栈中我们只会增加比辅助栈顶小于或等于的数，并且弹出时也有要求。

//前提都是在栈不为空时操作的
class MinStack {
	Stack<Integer> data;
	Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        data = new Stack<>();
        min = new Stack<>();
    }
    
    public void push(int x) {
    	data.add(x);
    	if(min.isEmpty()||x<=min.peek()) {
    		min.add(x);
    	}
    }
    //当我们弹出主栈元素时，要判断主栈元素是不是当前最小值，如果是，要把辅助栈也弹出
    public void pop() {
    	int x = data.pop();
    	if(min.peek().equals(x)) {
    		min.pop();
    	}
    }
    
    public int top() {
    	return data.peek();
    }
    //辅助栈顶就是最小值
    public int getMin() {
    	return min.peek();
    }
}