155. Min Stack

  • 27.1%

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

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.
1
2
3
4
5
6
7
8
9
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

方法一:

两个栈,其中一个为辅助栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MinStack {
private:
stack<int> s1;
stack<int> s2;
public:
/** initialize your data structure here. */
MinStack() {
}

void push(int x) {
s1.push(x);
if(s2.empty() || x<=getMin()) s2.push(x);
}

void pop() {
if(s1.top() == getMin()) s2.pop();
s1.pop();
}

int top() {
return s1.top();
}

int getMin() {
return s2.top();
}
};

我的代码实现:

两个stack,注意stack有pop top方法,但是没有front方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MinStack {
public:
stack<int> st1;
stack<int> st2;
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
st1.push(x);
if(st2.empty() || x<=st2.top())
st2.push(x);
}

void pop() {
int x = st1.top();
if(x==st2.top())
st2.pop();
st1.pop();
}

int top() {
return st1.top();
}

int getMin() {
return st2.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();
*/

方法二:

一个stack 一个int min

min表示当前的最小值,如果新的x不改变最小值,push进去。如果改变或者等于最小值,先把min压入,再把min更改为x,把x压入。

比如-2,0,-3
则对应的是

[-2], -2

[-2, 0], -2

[-2, 0, -2, -3] -3

弹出

[-2, 0, -2, -3] -3

[-2, 0] -2

[-2] -2

这种思路好,只是增加了一些存储空间而已。

pop时,检查与min的关系。

我的代码实现:

Dec 7th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class MinStack {
int min = INT_MAX;
stack<int> stack1;
public:
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
if(x<=min){
stack1.push(min);
min = x;
}
stack1.push(x);
}

void pop() {
int x = top();
stack1.pop();
if(x==min){
min = stack1.top();
stack1.pop();
}
}

int top() {
return stack1.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();
*/

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class MinStack {
public:
int min=INT_MAX;
stack<int> st;
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
if(x<=min){
st.push(min);
min = x;
}
st.push(x);
}

void pop() {
int x = st.top();
st.pop();
if(min == x){
min = st.top();
st.pop();
}
}

int top() {
return st.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代码,找时间改写为c++版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
public void push(int x) {
// only push the old minimum value when the current
// minimum value changes after pushing the new value x
if(x <= min){
stack.push(min);
min=x;
}
stack.push(x);
}

public void pop() {
// if pop operation could result in the changing of the current minimum value,
// pop twice and change the current minimum value to the last minimum value.
if(stack.pop() == min) min=stack.pop();
}

public int top() {
return stack.peek();
}

public int getMin() {
return min;
}
}

方法三:

一个stack,一个int min

此方法中,stack在空时,特殊处理。然后,对于新来的x,push其与min的差值,然后根据x与min 的差值决定更不更新min。pop时,相反处理。

相对于上一种方法,这种思想更加复杂一些,但是stack里保存的数据最少。

注意,java代码,找时间改写为c++版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class MinStack {
long min;
Stack<Long> stack;

public MinStack(){
stack=new Stack<>();
}

public void push(int x) {
if (stack.isEmpty()){
stack.push(0L);
min=x;
}else{
stack.push(x-min);//Could be negative if min value needs to change
if (x<min) min=x;
}
}

public void pop() {
if (stack.isEmpty()) return;

long pop=stack.pop();

if (pop<0) min=min-pop;//If negative, increase the min value

}

public int top() {
long top=stack.peek();
if (top>0){
return (int)(top+min);
}else{
return (int)(min);
}
}

public int getMin() {
return (int)min;
}
}

56ms, September 13, 2016

https://discuss.leetcode.com/topic/18556/c-using-two-stacks-quite-short-and-easy-to-understand

C++ using two stacks, quite short and easy to understand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MinStack {
private:
stack<int> s1;
stack<int> s2;
public:
/** initialize your data structure here. */
MinStack() {
}

void push(int x) {
s1.push(x);
if(s2.empty() || x<=getMin()) s2.push(x);
}

void pop() {
if(s1.top() == getMin()) s2.pop();
s1.pop();
}

int top() {
return s1.top();
}

int getMin() {
return s2.top();
}
};

https://discuss.leetcode.com/topic/28435/c-o-1-solution

C++ O(1) solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MinStack {
public:
vector<int> a;
vector<int> min;
MinStack() {
min.push_back(2147483647);
}
void push(int x) {
a.push_back(x);
if (x < min.back()) {
min.push_back(x);
} else {
min.push_back(min.back());
}
}

void pop() {
a.pop_back();
min.pop_back();
}

int top() {
return a.back();
}

int getMin() {
return min.back();
}
};

https://discuss.leetcode.com/topic/11985/my-python-solution

My Python solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MinStack:

def __init__(self):
self.q = []

# @param x, an integer
# @return an integer
def push(self, x):
curMin = self.getMin()
if curMin == None or x < curMin:
curMin = x
self.q.append((x, curMin));

# @return nothing
def pop(self):
self.q.pop()


# @return an integer
def top(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q) - 1][0]


# @return an integer
def getMin(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q) - 1][1]

https://discuss.leetcode.com/topic/4953/share-my-java-solution-with-only-one-stack

Share my Java solution with ONLY ONE stack

The question is ask to construct One stack. So I am using one stack.

The idea is to store the gap between the min value and the current value;

The problem for my solution is the cast. I have no idea to avoid the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class MinStack {
long min;
Stack<Long> stack;

public MinStack(){
stack=new Stack<>();
}

public void push(int x) {
if (stack.isEmpty()){
stack.push(0L);
min=x;
}else{
stack.push(x-min);//Could be negative if min value needs to change
if (x<min) min=x;
}
}

public void pop() {
if (stack.isEmpty()) return;

long pop=stack.pop();

if (pop<0) min=min-pop;//If negative, increase the min value

}

public int top() {
long top=stack.peek();
if (top>0){
return (int)(top+min);
}else{
return (int)(min);
}
}

public int getMin() {
return (int)min;
}
}

https://discuss.leetcode.com/topic/7020/java-accepted-solution-using-one-stack

Java accepted solution using one stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
public void push(int x) {
// only push the old minimum value when the current
// minimum value changes after pushing the new value x
if(x <= min){
stack.push(min);
min=x;
}
stack.push(x);
}

public void pop() {
// if pop operation could result in the changing of the current minimum value,
// pop twice and change the current minimum value to the last minimum value.
if(stack.pop() == min) min=stack.pop();
}

public int top() {
return stack.peek();
}

public int getMin() {
return min;
}
}
谢谢你,可爱的朋友。