155. 最小栈

题目

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。

• void push(int val) 将元素val推入堆栈。

• void pop() 删除堆栈顶部的元素。

• int top() 获取堆栈顶部的元素。

• int getMin() 获取堆栈中的最小元素。

示例1：

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

提示：

• -2^31 <= val <= 2^31 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 10^4 次

解法

解法一：

借用Java自带的Stack，使用一个辅助栈，保存当前最小元素。

Java

class MinStack {
	private Stack<Integer> data;
	private Stack<Integer> helper;

	public MinStack() {
		data = new Stack<>();
		helper = new Stack<>();
	}

	public void push(int x) {
		data.add(x);
		if (helper.isEmpty() || helper.peek() >= x) {
			helper.add(x);
		}
	}

	public void pop() {
		if (!data.isEmpty()) {
			int top = data.pop();
			if (top == helper.peek()) {
				helper.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("栈中元素为空，此操作非法");
	}
}

解法二：

在遇到比min更小的值时，才把min入栈

Java

class MinStack {
	int min = Integer.MAX_VALUE;
	Stack<Integer> stack = new Stack<Integer>();

	public void push(int x) {
		// only push the old minimum value when the current
		// minimum value changes after pushing the new value x
		if (x <= min) {
			stack.push(min);
			min = x;
		}
		stack.push(x);
	}

	public void pop() {
		// if pop operation could result in the changing of the current minimum
		// value,
		// pop twice and change the current minimum value to the last minimum
		// value.
		if (stack.pop() == min)
			min = stack.pop();
	}

	public int top() {
		return stack.peek();
	}

	public int getMin() {
		return min;
	}
}