0155. 最小栈
题目地址(155. 最小栈)
题目描述
1
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
2
3
push(x) —— 将元素 x 推入栈中。
4
pop() —— 删除栈顶的元素。
5
top() —— 获取栈顶元素。
6
getMin() —— 检索栈中的最小元素。
7
8
9
示例:
10
11
输入：
12
["MinStack","push","push","push","getMin","pop","top","getMin"]
13
[[],[-2],[0],[-3],[],[],[],[]]
14
15
输出：
16
[null,null,null,null,-3,null,0,-2]
17
18
解释：
19
MinStack minStack = new MinStack();
20
minStack.push(-2);
21
minStack.push(0);
22
minStack.push(-3);
23
minStack.getMin(); --> 返回 -3.
24
minStack.pop();
25
minStack.top(); --> 返回 0.
26
minStack.getMin(); --> 返回 -2.
27
28
29
提示：
30
31
pop、top 和 getMin 操作总是在 非空栈 上调用。
Copied!
前置知识
公司
- amazon
- bloomberg
- google
- snapchat
- uber
- zenefits
- 阿里
- 腾讯
- 百度
- 字节
两个栈
思路
我们使用两个栈：
- 一个栈存放全部的元素，push，pop都是正常操作这个正常栈。
- 另一个存放最小栈。 每次push，如果比最小栈的栈顶还小，我们就push进最小栈，否则不操作
- 每次pop的时候，我们都判断其是否和最小栈栈顶元素相同，如果相同，那么我们pop掉最小栈的栈顶元素即可
关键点
- 往minstack中 push的判断条件。 应该是stack为空或者x小于等于minstack栈顶元素
代码
- 语言支持：JS，C++，Java，Python
JavaScript Code:
1
/**
2
* initialize your data structure here.
3
*/
4
var MinStack = function() {
5
this.stack = []
6
this.minStack = []
7
};
8
9
/**
10
* @param {number} x
11
* @return {void}
12
*/
13
MinStack.prototype.push = function(x) {
14
this.stack.push(x)
15
if (this.minStack.length == 0 || x <= this.minStack[this.minStack.length - 1]) {
16
this.minStack.push(x)
17
}
18
};
19
20
/**
21
* @return {void}
22
*/
23
MinStack.prototype.pop = function() {
24
const x = this.stack.pop()
25
if (x !== void 0 && x === this.minStack[this.minStack.length - 1]) {
26
this.minStack.pop()
27
}
28
};
29
30
/**
31
* @return {number}
32
*/
33
MinStack.prototype.top = function() {
34
return this.stack[this.stack.length - 1]
35
};
36
37
/**
38
* @return {number}
39
*/
40
MinStack.prototype.min = function() {
41
return this.minStack[this.minStack.length - 1]
42
};
43
44
/**
45
* Your MinStack object will be instantiated and called as such:
46
* var obj = new MinStack()
47
* obj.push(x)
48
* obj.pop()
49
* var param_3 = obj.top()
50
* var param_4 = obj.min()
51
*/
Copied!
C++ Code:
1
class MinStack {
2
stack<int> data;
3
stack<int> helper;
4
public:
5
/** initialize your data structure here. */
6
MinStack() {
7
8
}
9
10
void push(int x) {
11
data.push(x);
12
if(helper.empty() || helper.top() >= x)
13
{
14
helper.push(x);
15
}
16
17
}
18
19
void pop() {
20
int top = data.top();
21
data.pop();
22
if(top == helper.top())
23
{
24
helper.pop();
25
}
26
27
}
28
29
int top() {
30
return data.top();
31
}
32
33
int getMin() {
34
return helper.top();
35
}
36
};
37
38
/**
39
* Your MinStack object will be instantiated and called as such:
40
* MinStack* obj = new MinStack();
41
* obj->push(x);
42
* obj->pop();
43
* int param_3 = obj->top();
44
* int param_4 = obj->getMin();
45
*/
Copied!
Java Code:
1
public class MinStack {
2
3
// 数据栈
4
private Stack<Integer> data;
5
// 辅助栈
6
private Stack<Integer> helper;
7
8
/**
9
* initialize your data structure here.
10
*/
11
public MinStack() {
12
data = new Stack<>();
13
helper = new Stack<>();
14
}
15
16
public void push(int x) {
17
// 辅助栈在必要的时候才增加
18
data.add(x);
19
if (helper.isEmpty() || helper.peek() >= x) {
20
helper.add(x);
21
}
22
}
23
24
public void pop() {
25
// 关键 3：data 一定得 pop()
26
if (!data.isEmpty()) {
27
// 注意：声明成 int 类型，这里完成了自动拆箱，从 Integer 转成了 int，
28
// 因此下面的比较可以使用 "==" 运算符
29
int top = data.pop();
30
if(top == helper.peek()){
31
helper.pop();
32
}
33
}
34
}
35
36
public int top() {
37
if(!data.isEmpty()){
38
return data.peek();
39
}
40
}
41
42
public int getMin() {
43
if(!helper.isEmpty()){
44
return helper.peek();
45
}
46
}
47
}
Copied!
Python3 Code:
1
class MinStack:
2
3
def __init__(self):
4
"""
5
initialize your data structure here.
6
"""
7
self.stack = []
8
self.minstack = []
9
10
def push(self, x: int) -> None:
11
self.stack.append(x)
12
if not self.minstack or x <= self.minstack[-1]:
13
self.minstack.append(x)
14
15
def pop(self) -> None:
16
tmp = self.stack.pop()
17
if tmp == self.minstack[-1]:
18
self.minstack.pop()
19
20
def top(self) -> int:
21
return self.stack[-1]
22
23
def min(self) -> int:
24
return self.minstack[-1]
25
26
27
# Your MinStack object will be instantiated and called as such:
28
# obj = MinStack()
29
# obj.push(x)
30
# obj.pop()
31
# param_3 = obj.top()
32
# param_4 = obj.min()
Copied!
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
一个栈
思路
符合直觉的方法是，每次对栈进行修改操作（push和pop）的时候更新最小值。 然后getMin只需要返回我们计算的最小值即可， top也是直接返回栈顶元素即可。 这种做法每次修改栈都需要更新最小值，因此时间复杂度是O(n).
Could not load image
是否有更高效的算法呢？答案是有的。
我们每次入栈的时候，保存的不再是真正的数字，而是它与当前最小值的差（当前元素没有入栈的时候的最小值）。 这样我们pop和top的时候拿到栈顶元素再加上上一个最小值即可。 另外我们在push和pop的时候去更新min，这样getMin的时候就简单了，直接返回min。
注意上面加粗的“上一个”，不是“当前的最小值”
经过上面的分析，问题的关键转化为“如何求得上一个最小值”，解决这个的关键点在于利用min。
pop或者top的时候：
- 如果栈顶元素小于0，说明栈顶是当前最小的元素，它出栈会对min造成影响，我们需要去更新min。 上一个最小的是“min - 栈顶元素”,我们需要将上一个最小值更新为当前的最小值因为栈顶元素入栈的时候的通过
栈顶元素 = 真实值 - 上一个最小的元素得到的， 而真实值 = min， 因此可以得出上一个最小的元素 = 真实值 -栈顶元素 - 如果栈顶元素大于0，说明它对最小值
没有影响，上一个最小值就是上上个最小值。
关键点
- 最小栈存储的不应该是真实值，而是真实值和min的差值
- top的时候涉及到对数据的还原，这里千万注意是上一个最小值
代码
- 语言支持：JS，C++，Java，Python
Javascript Code:
1
/*
2
* @lc app=leetcode id=155 lang=javascript
3
*
4
* [155] Min Stack
5
*/
6
/**
7
* initialize your data structure here.
8
*/
9
var MinStack = function() {
10
this.stack = [];
11
this.minV = Number.MAX_VALUE;
12
};
13
14
/**
15
* @param {number} x
16
* @return {void}
17
*/
18
MinStack.prototype.push = function(x) {
19
// update 'min'
20
const minV = this.minV;
21
if (x < this.minV) {
22
this.minV = x;
23
}
24
return this.stack.push(x - minV);
25
};
26
27
/**
28
* @return {void}
29
*/
30
MinStack.prototype.pop = function() {
31
const item = this.stack.pop();
32
const minV = this.minV;
33
34
if (item < 0) {
35
this.minV = minV - item;
36
return minV;
37
}
38
return item + minV;
39
};
40
41
/**
42
* @return {number}
43
*/
44
MinStack.prototype.top = function() {
45
const item = this.stack[this.stack.length - 1];
46
const minV = this.minV;
47
48
if (item < 0) {
49
return minV;
50
}
51
return item + minV;
52
};
53
54
/**
55
* @return {number}
56
*/
57
MinStack.prototype.min = function() {
58
return this.minV;
59
};
60
61
/**
62
* Your MinStack object will be instantiated and called as such:
63
* var obj = new MinStack()
64
* obj.push(x)
65
* obj.pop()
66
* var param_3 = obj.top()
67
* var param_4 = obj.min()
68
*/
Copied!
C++ Code:
1
class MinStack {
2
stack<long> data;
3
long min = INT_MAX;
4
public:
5
/** initialize your data structure here. */
6
MinStack() {
7
8
}
9
10
void push(int x) {
11
data.push(x - min);
12
if(x < min)
13
{
14
min = x;
15
}
16
17
}
18
19
void pop() {
20
long top = data.top();
21
data.pop();
22
// 更新最小值
23
if(top < 0)
24
{
25
min -= top;
26
}
27
28
}
29
30
int top() {
31
long top = data.top();
32
// 最小值为 min
33
if (top < 0)
34
{
35
return min;
36
}
37
else{
38
return min+top;
39
}
40
}
41
42
int getMin() {
43
return min;
44
}
45
};
46
47
/**
48
* Your MinStack object will be instantiated and called as such:
49
* MinStack* obj = new MinStack();
50
* obj->push(x);
51
* obj->pop();
52
* int param_3 = obj->top();
53
* int param_4 = obj->getMin();
54
*/
Copied!
Java Code:
1
class MinStack {
2
long min;
3
Stack<Long> stack;
4
5
/** initialize your data structure here. */
6
public MinStack() {
7
stack = new Stack<>();
8
}
9
10
public void push(int x) {
11
if (stack.isEmpty()) {
12
stack.push(0L);
13
min = x;
14
}
15
else {
16
stack.push(x - min);
17
if (x < min)
18
min = x;
19
}
20
}
21
22
public void pop() {
23
long p = stack.pop();
24
25
if (p < 0) {
26
// if (p < 0), the popped value is the min
27
// Recall p is added by this statement: stack.push(x - min);
28
// So, p = x - old_min
29
// old_min = x - p
30
// again, if (p < 0), x is the min so:
31
// old_min = min - p
32
min = min - p;
33
}
34
}
35
36
public int top() {
37
long p = stack.peek();
38
39
if (p < 0) {
40
return (int) min;
41
}
42
else {
43
// p = x - min
44
// x = p + min
45
return (int) (p + min);
46
}
47
}
48
49
public int getMin() {
50
return (int) min;
51
}
52
}
Copied!
Python Code:
1
class MinStack:
2
3
def __init__(self):
4
"""
5
initialize your data structure here.
6
"""
7
self.minV = float('inf')
8
self.stack = []
9
10
def push(self, x: int) -> None:
11
self.stack.append(x - self.minV)
12
if x < self.minV:
13
self.minV = x
14
15
def pop(self) -> None:
16
if not self.stack:
17
return
18
tmp = self.stack.pop()
19
if tmp < 0:
20
self.minV -= tmp
21
22
def top(self) -> int:
23
if not self.stack:
24
return
25
tmp = self.stack[-1]
26
if tmp < 0:
27
return self.minV
28
else:
29
return self.minV + tmp
30
31
def min(self) -> int:
32
return self.minV
33
34
35
36
# Your MinStack object will be instantiated and called as such:
37
# obj = MinStack()
38
# obj.push(x)
39
# obj.pop()
40
# param_3 = obj.top()
41
# param_4 = obj.min()
Copied!
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
Could not load image
最近更新 1yr ago