最小栈（155）

题目

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

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

示例

输入：

["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

提示

pop、top 和 getMin 操作总是在 非空栈 上调用。

算法

因为需要在常数时间内检索到最小元素，所以我们维护一个表示当前最小值的栈min，每当推入一个比当前所有元素都小的值的时候，我们将这个当前最小值推入min的栈顶；如果推入的值不是当前已入栈元素的最小值，那么我们重复推入当前最小值到min中，这样我们在getMin()时总是返回栈顶元素即可；当我们使用pop()弹出栈元素时，我们同时弹出min栈顶的元素即可。

等于栈min维护了一个最小值，这个最小值是栈中保存了对应数量元素时的最小值

/**
 * initialize your data structure here.
 */
var MinStack = function () {
	this.stack = [];
	this.min = [+Infinity];
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
	this.stack.push(x);
	this.min.push(Math.min(this.min[this.min.length - 1], x));
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
	this.stack.pop();
	this.min.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
	return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
	return this.min[this.min.length - 1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */