刷leetcode-最小的栈 | 刷题打卡
一、题目描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
提示：
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.
二、思路分析：
其实开始怎么也不明白，常数时间内怎么拿到最小值。
这里妙就妙在，这是个栈
栈的特点：先进后出
于是，来个辅助栈来存放原栈的『当前及历史最小值』
每次主栈有新值进来的时候，和历史最小值比较下，新值小的话，新值推到辅助栈，新值大的话，将历史最小值再次推到辅助栈。
每次主栈推出值的时候，辅助栈也推出一个值，因为每次最小值总是『当前及历史的最小值』，如果是当前的值推出去也没啥，如果是剩下的值，推出去更没啥，因为辅助栈的下一个肯定还是她
所以很好的利用了，栈的先进后出的特性
这样的话，空间复杂度是O(n)，时间复杂度是O(1)
三、AC 代码：
/** * initialize your data structure here. */ var MinStack = function() { this.array = [] this.mini_array = [Infinity] }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { this.array.push(x) this.mini_array.push(Math.min(x,this.mini_array[this.mini_array.length-1])) }; /** * @return {void} */ MinStack.prototype.pop = function() { this.array.pop() this.mini_array.pop() }; /** * @return {number} */ MinStack.prototype.top = function() { return this.array[this.array.length-1] }; /** * @return {number} */ MinStack.prototype.getMin = function() { return this.mini_array[this.mini_array.length-1] };
四、总结：
- 栈有先进后出的特点，所以可以利用辅助栈来存放原栈的『当前及历史最小值』
- mini_array里默认需要放一个Infinity
