155.最小栈

题目：

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

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

方法一：辅助栈

使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

• 当一个元素要push时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值：
  • 当前元素 > 当前辅助栈的栈顶存储的最小值，当前元素只push到元素栈中；
  • 当前元素 <= 当前辅助栈的栈顶存储的最小值，当前元素一起push到辅助栈中；
• 当一个元素要pop时：
  • 当前元素 > 当前辅助栈的栈顶存储的最小值，只pop元素栈栈顶元素；
  • 当前元素 <= 当前辅助栈的栈顶存储的最小值，把辅助栈的栈顶元素也一起pop；
• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

class MinStack {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public MinStack() {
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }
    
    public void push(int val) {
        if(this.stackMin.isEmpty()){
            this.stackMin.push(val);
            this.stackData.push(val);
            return;
        }
        if(val > this.getMin()){
            this.stackData.push(val);
        }else{
            this.stackData.push(val);
            this.stackMin.push(val);
        }
    }
    
    public void pop() {
        if(this.stackData.isEmpty()){
            return;
        }
        if(this.top() > this.getMin()){
            this.stackData.pop();
        }else{
            this.stackData.pop();
            this.stackMin.pop();
        }
    }
    
    public int top() {
        if(this.stackData.isEmpty()){
            return -1;
        }
        return this.stackData.peek();
    }
    
    public int getMin() {
        return this.stackMin.peek();
    }
}

复杂度分析

• 时间复杂度O(1)：因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。
• 空间复杂度O(n)：n为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。

方法二：差值法

详细通俗的思路分析，多解法 - 最小栈 - 力扣（LeetCode） (leetcode-cn.com)

有没有空间复杂度为O(1)，不用辅助栈的方法呢？

有！

用一个 min 变量保存最小值。栈中不去保存原来的值，而是去存储入元素的真实值和当前最小值的差值。然后我们就可以通过 min 值和栈顶元素得到之前的最小值。

算法：

入栈

• 我们每次存入的是 元素的真实值 - 当前最小值。然后再更新最小值。

出栈

• 当 元素的真实值 >= 当前最小值 的时候，我们存入的肯定就是非负数，所以 元素真实值 = 栈中的值 + 当前最小值 。
• 当 元素的真实值 < 当前最小值 的时候，我们存入的肯定就是负值，所以 元素真实值 = 当前最小值 。这个元素出栈后，还要还原当前最小值：当前最小值= 当前最小值 - 栈顶元素。

举例：

这里数据类型要为long，因为我们保存的是差值，所以可能造成溢出，比如以下测试用例：

["MinStack","push","push","getMin"]
[[],[2147483647],[-2147483648],[]]

当栈中push进2147483647时，栈中存入0，min=2147483647，然后再push进-2147483648，-2147483648 - 2147483647 就超出了int范围 [-2147483648, 2147483647]。所以应该用数据范围更大的 long 类型。

public class MinStack {
    long min;
	Stack<Long> stack;

	public MinStack(){
        this.stack = new Stack<>();
    }

	public void push(int val) {
		if (stack.isEmpty()) {
			min = val;
            stack.push(val - min);
		} else {
            stack.push(val - min);
			if (val < min){
				min = val; // 更新最小值
			}
		}
	}

	public void pop() {
		if (stack.isEmpty()){
			return;
        }

		long popVal = stack.pop();
		//弹出的是负值，要更新 min
		if (popVal < 0) {
			min = min - popVal;
		}
	}

	public int top() {
		long topVal = stack.peek();
		if (topVal < 0) {
		    //负数的话，出栈的值保存在 min 中
			return (int) (min);
		} else {
            //出栈元素加上最小值即可
			return (int) (min + topVal);
		}
	}

	public int getMin() {
		return (int) min;
	}
}

复杂度分析

• 时间复杂度O(1)：栈的插入、删除与读取操作都是 O(1)，每个操作最多调用栈操作一次。
• 空间复杂度O(1)：只需要记录当前最小值min，并不需要额外空间。