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)
更多题解可以访问我的LeetCode题解仓库:https://github.com/azl397985856/leetcode 。 目前已经37K star啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
Could not load image