题目地址()
题目描述
设计一个支持 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 操作总是在 非空栈 上调用。
难度:Middle
前置知识
公司
- amazon
- bloomberg
- snapchat
- uber
- zenefits
- 阿里
- 腾讯
- 百度
- 字节
两个栈
思路
我们使用两个栈:
- 一个栈存放全部的元素,push,pop都是正常操作这个正常栈。
- 另一个存放最小栈。 每次push,如果比最小栈的栈顶还小,我们就push进最小栈,否则不操作
- 每次pop的时候,我们都判断其是否和最小栈栈顶元素相同,如果相同,那么我们pop掉最小栈的栈顶元素即可
关键点
- 往minstack中 push的判断条件。 应该是stack为空或者x小于等于minstack栈顶元素
代码
- 语言支持:JS,C++,Java,Python
JavaScript Code:
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* initialize your data structure here.
*/
var MinStack = 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() {
const x = this.stack.pop()
if (x !== void 0 && x === this.minStack[this.minStack.length - 1]) {
this.minStack.pop()
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1]
};
/**
* @return {number}
*/
MinStack.prototype.min = function() {
return this.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:
class MinStack {
stack<int> data;
stack<int> helper;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
data.push(x);
if(helper.empty() || helper.top() >= x)
{
helper.push(x);
}
}
void pop() {
int top = data.top();
data.pop();
if(top == helper.top())
{
helper.pop();
}
}
int top() {
return data.top();
}
int getMin() {
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:
public class MinStack {
// 数据栈
private Stack<Integer> data;
// 辅助栈
private Stack<Integer> helper;
/**
* initialize your data structure here.
*/
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() {
// 关键 3:data 一定得 pop()
if (!data.isEmpty()) {
// 注意:声明成 int 类型,这里完成了自动拆箱,从 Integer 转成了 int,
// 因此下面的比较可以使用 "==" 运算符
int top = data.pop();
if(top == helper.peek()){
helper.pop();
}
}
}
public int top() {
if(!data.isEmpty()){
return data.peek();
}
}
public int getMin() {
if(!helper.isEmpty()){
return helper.peek();
}
}
}
Python3 Code:
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.minstack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.minstack or x <= self.minstack[-1]:
self.minstack.append(x)
def pop(self) -> None:
tmp = self.stack.pop()
if tmp == self.minstack[-1]:
self.minstack.pop()
def top(self) -> int:
return self.stack[-1]
def min(self) -> int:
return self.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.
*/
var MinStack = function() {
this.stack = [];
this.minV = Number.MAX_VALUE;
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
// update 'min'
const minV = this.minV;
if (x < this.minV) {
this.minV = x;
}
return this.stack.push(x - minV);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
const item = this.stack.pop();
const minV = this.minV;
if (item < 0) {
this.minV = minV - item;
return minV;
}
return item + minV;
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
const item = this.stack[this.stack.length - 1];
const minV = this.minV;
if (item < 0) {
return minV;
}
return item + minV;
};
/**
* @return {number}
*/
MinStack.prototype.min = function() {
return this.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:
class MinStack {
stack<long> data;
long min = INT_MAX;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
data.push(x - min);
if(x < min)
{
min = x;
}
}
void pop() {
long top = data.top();
data.pop();
// 更新最小值
if(top < 0)
{
min -= top;
}
}
int top() {
long top = data.top();
// 最小值为 min
if (top < 0)
{
return min;
}
else{
return min+top;
}
}
int getMin() {
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:
class MinStack {
long min;
Stack<Long> stack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(0L);
min = x;
}
else {
stack.push(x - min);
if (x < min)
min = x;
}
}
public void pop() {
long p = 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 - p
min = min - p;
}
}
public int top() {
long p = stack.peek();
if (p < 0) {
return (int) min;
}
else {
// p = x - min
// x = p + min
return (int) (p + min);
}
}
public int getMin() {
return (int) min;
}
}
Python Code:
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.minV = float('inf')
self.stack = []
def push(self, x: int) -> None:
self.stack.append(x - self.minV)
if x < self.minV:
self.minV = x
def pop(self) -> None:
if not self.stack:
return
tmp = self.stack.pop()
if tmp < 0:
self.minV -= tmp
def top(self) -> int:
if not self.stack:
return
tmp = self.stack[-1]
if tmp < 0:
return self.minV
else:
return self.minV + tmp
def min(self) -> int:
return self.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://leetcode-cn.com/problems/min-stack/
- 更多力扣 解题: 力扣 – 全球极客挚爱的技术成长平台 ,也可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books,标星关注一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com