155.min-stack.md

题目地址(155. 最小栈)

https://leetcode-cn.com/problems/min-stack/

题目描述

设计一个支持 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 操作总是在 非空栈 上调用。 

前置知识

• 栈

公司

• amazon
• bloomberg
• google
• snapchat
• uber
• zenefits
• 阿里
• 腾讯
• 百度
• 字节

两个栈

思路

我们使用两个栈：

• 一个栈存放全部的元素，push，pop都是正常操作这个正常栈。
• 另一个存放最小栈。 每次push，如果比最小栈的栈顶还小，我们就push进最小栈，否则不操作
• 每次pop的时候，我们都判断其是否和最小栈栈顶元素相同，如果相同，那么我们pop掉最小栈的栈顶元素即可

关键点

• 往minstack中 push的判断条件。 应该是stack为空或者x小于等于minstack栈顶元素

代码

• 语言支持：JS，C++，Java，Python

JavaScript Code:

/** * initialize your data structure here. */varMinStack=function(){this.stack=[]this.minStack=[]};/**  * @param {number} x * @return {void} */MinStack.prototype.push=function(x){this.stack.push(x)if(this.minStack.length==0||x<=this.minStack[this.minStack.length-1]){this.minStack.push(x)}};/** * @return {void} */MinStack.prototype.pop=function(){constx=this.stack.pop()if(x!==void0&&x===this.minStack[this.minStack.length-1]){this.minStack.pop()}};/** * @return {number} */MinStack.prototype.top=function(){returnthis.stack[this.stack.length-1]};/** * @return {number} */MinStack.prototype.min=function(){returnthis.minStack[this.minStack.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.min() */

C++ Code:

classMinStack { stack<int> data; stack<int> helper; public:/** initialize your data structure here. */MinStack() { } voidpush(int x) { data.push(x); if(helper.empty() || helper.top() >= x) { helper.push(x); } } voidpop() { int top = data.top(); data.pop(); if(top == helper.top()) { helper.pop(); } } inttop() { return data.top(); } intgetMin() { return helper.top(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin();*/

Java Code:

publicclassMinStack { // 数据栈privateStack<Integer> data; // 辅助栈privateStack<Integer> helper; /** * initialize your data structure here. */publicMinStack() { data = newStack<>(); helper = newStack<>(); } publicvoidpush(intx) { // 辅助栈在必要的时候才增加data.add(x); if (helper.isEmpty() || helper.peek() >= x) { helper.add(x); } } publicvoidpop() { // 关键 3：data 一定得 pop()if (!data.isEmpty()) { // 注意：声明成 int 类型，这里完成了自动拆箱，从 Integer 转成了 int，// 因此下面的比较可以使用 "==" 运算符inttop = data.pop(); if(top == helper.peek()){ helper.pop(); } } } publicinttop() { if(!data.isEmpty()){ returndata.peek(); } } publicintgetMin() { if(!helper.isEmpty()){ returnhelper.peek(); } } }

Python3 Code:

classMinStack: def__init__(self): """ initialize your data structure here. """self.stack= [] self.minstack= [] defpush(self, x: int) ->None: self.stack.append(x) ifnotself.minstackorx<=self.minstack[-1]: self.minstack.append(x) defpop(self) ->None: tmp=self.stack.pop() iftmp==self.minstack[-1]: self.minstack.pop() deftop(self) ->int: returnself.stack[-1] defmin(self) ->int: returnself.minstack[-1] # Your MinStack object will be instantiated and called as such:# obj = MinStack()# obj.push(x)# obj.pop()# param_3 = obj.top()# param_4 = obj.min()

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(1)

一个栈

思路

符合直觉的方法是，每次对栈进行修改操作（push和pop）的时候更新最小值。 然后getMin只需要返回我们计算的最小值即可， top也是直接返回栈顶元素即可。 这种做法每次修改栈都需要更新最小值，因此时间复杂度是O(n).

是否有更高效的算法呢？答案是有的。

我们每次入栈的时候，保存的不再是真正的数字，而是它与当前最小值的差（当前元素没有入栈的时候的最小值）。 这样我们pop和top的时候拿到栈顶元素再加上上一个最小值即可。 另外我们在push和pop的时候去更新min，这样getMin的时候就简单了，直接返回min。

注意上面加粗的“上一个”，不是“当前的最小值”

经过上面的分析，问题的关键转化为“如何求得上一个最小值”，解决这个的关键点在于利用min。

pop或者top的时候：

• 如果栈顶元素小于0，说明栈顶是当前最小的元素，它出栈会对min造成影响，我们需要去更新min。 上一个最小的是“min - 栈顶元素”,我们需要将上一个最小值更新为当前的最小值

因为栈顶元素入栈的时候的通过 栈顶元素 = 真实值 - 上一个最小的元素 得到的， 而真实值 = min， 因此可以得出上一个最小的元素 = 真实值 -栈顶元素

• 如果栈顶元素大于0，说明它对最小值没有影响，上一个最小值就是上上个最小值。

关键点

• 最小栈存储的不应该是真实值，而是真实值和min的差值
• top的时候涉及到对数据的还原，这里千万注意是上一个最小值

代码

• 语言支持：JS，C++，Java，Python

Javascript Code:

/* * @lc app=leetcode id=155 lang=javascript * * [155] Min Stack *//** * initialize your data structure here. */varMinStack=function(){this.stack=[];this.minV=Number.MAX_VALUE;};/** * @param {number} x * @return {void} */MinStack.prototype.push=function(x){// update 'min'constminV=this.minV;if(x<this.minV){this.minV=x;}returnthis.stack.push(x-minV);};/** * @return {void} */MinStack.prototype.pop=function(){constitem=this.stack.pop();constminV=this.minV;if(item<0){this.minV=minV-item;returnminV;}returnitem+minV;};/** * @return {number} */MinStack.prototype.top=function(){constitem=this.stack[this.stack.length-1];constminV=this.minV;if(item<0){returnminV;}returnitem+minV;};/** * @return {number} */MinStack.prototype.min=function(){returnthis.minV;};/** * 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.min() */

C++ Code:

classMinStack { stack<long> data; long min = INT_MAX; public:/** initialize your data structure here. */MinStack() { } voidpush(int x) { data.push(x - min); if(x < min) { min = x; } } voidpop() { long top = data.top(); data.pop(); // 更新最小值if(top < 0) { min -= top; } } inttop() { long top = data.top(); // 最小值为 minif (top < 0) { return min; } else{ return min+top; } } intgetMin() { return min; } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin();*/

Java Code:

classMinStack { longmin; Stack<Long> stack; /** initialize your data structure here. */publicMinStack() { stack = newStack<>(); } publicvoidpush(intx) { if (stack.isEmpty()) { stack.push(0L); min = x; } else { stack.push(x - min); if (x < min) min = x; } } publicvoidpop() { longp = stack.pop(); if (p < 0) { // if (p < 0), the popped value is the min// Recall p is added by this statement: stack.push(x - min);// So, p = x - old_min// old_min = x - p// again, if (p < 0), x is the min so:// old_min = min - pmin = min - p; } } publicinttop() { longp = stack.peek(); if (p < 0) { return (int) min; } else { // p = x - min// x = p + minreturn (int) (p + min); } } publicintgetMin() { return (int) min; } }

Python Code:

classMinStack: def__init__(self): """ initialize your data structure here. """self.minV=float('inf') self.stack= [] defpush(self, x: int) ->None: self.stack.append(x-self.minV) ifx<self.minV: self.minV=xdefpop(self) ->None: ifnotself.stack: returntmp=self.stack.pop() iftmp<0: self.minV-=tmpdeftop(self) ->int: ifnotself.stack: returntmp=self.stack[-1] iftmp<0: returnself.minVelse: returnself.minV+tmpdefmin(self) ->int: returnself.minV# Your MinStack object will be instantiated and called as such:# obj = MinStack()# obj.push(x)# obj.pop()# param_3 = obj.top()# param_4 = obj.min()

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(1)

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经37K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。