壹 ? 引
本题来自LeetCode155. 最小栈，难度简单，题目描述如下：
设计一个支持 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 操作总是在 非空栈 上调用。
贰 ? 使用数组API模拟
题目要求其实很简单，自己实现一个支持入栈，出栈，获取栈顶元素以及获取栈内最小元素的栈结构。
我们都知道栈是先进后出，就像俄罗斯方块一样，先入栈的总是在栈底，所以出栈时，总是最后入栈的先出栈，最后出栈的总是最早入栈的元素。因此我们完全可以使用一个数组模拟这个过程，我们使用shift模拟出栈，使用unshift模拟入栈，top是获取栈顶元素，这里我们可以直接使用arr[0]来实现这个方法，抛开题目使用常数时间检索最小值的要求，其实我们可以使用Math.min来检索栈内最小元素。
废话不多说，先上一个基本实现的代码：
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.nums = [];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
// 模拟入栈
this.nums.unshift(val);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
// 模拟出栈
this.nums.shift();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
// 模拟top
return this.nums[0];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return Math.min(...this.nums);
};
以上代码能满足基本要求，但并未达到查找最小数时常数时间的要求。何为常数时间复杂度，其实就是O(1)。我们往栈内添加元素的行为只有一种，也就是push，所以如果要达到要求，其实可以在这一步做点小操作，比如每次入栈的时候都计算当前的最小值，并随着当前入栈的值组成一个新数组，一起入栈。
假设我们入栈操作一共做了三次，入栈的数字为1，3，0，那么这个过程就是：
1开始入栈了，由于此时是空栈，那么最小值就是1自己，于是我们入栈元素为[1,1]，整个栈此时为[[1,1]]
3开始入栈了，此时栈并不是空栈，最小值自然是栈顶元素[1,1][1]与3做比较，很明显1更小，于是入栈[3,1]，此时栈为[[3,1],[1,1]]。
0开始入栈了，栈顶元素的第二个数字永远是当前栈的最小值，因此我们需要拿0和1比较，很明显0更小，于是入栈[0,0]，此时栈为[[0,0],[3,1],[1,1]]。
如果我们要获取当前栈最小元素，永远可以通过获取栈顶元素的第二个数字，它就是当前最小数。假设[0,0]出栈了，那么当前最小数就是1，完全没问题。
让我们实现这个代码：
/**
* initialize your data structure here.
*/
var MinStack = function () {
this.nums = [];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function (val) {
// 假设是空栈，最小的就是自己，反之与栈顶元素的第二个数字进行比较
if (this.nums.length) {
this.nums.unshift([val, Math.min(val, this.nums[0][1])])
} else {
this.nums.unshift([val, val]);
};
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
this.nums.shift();
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.nums[0][0];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
// 常数时间获取栈内最小值
return this.nums[0][1];
};
那么本题就分析到这里了。