LeetCode 155. Min Stack 剑指Offer 30. 包含 min 函数的栈 [Easy]

带取最小值功能的栈。

题目来源:https://leetcode.com/problems/min-stack

题目难度:Easy

解答1:

核心思想

使用两个栈,一个数据栈,一个最小值栈。push 的时候,如果小于等于当前最小值,同时压入两个栈,然后每次弹出的时候,数据栈弹出的数和最小值栈的栈顶作比较,如果相同,那么把最小值也弹出。

代码

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
44
45
46
47
48
49
50
51
52
53
import java.util.ArrayDeque;
import java.util.Deque;

public class MinStack {
private Deque<Integer> stackData;
private Deque<Integer> stackMin;

/** initialize your data structure here. */
public MinStack() {
this.stackData = new ArrayDeque<>();
this.stackMin = new ArrayDeque<>();
}

public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum <= this.getMin()) {
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}

public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
int value = this.stackData.pop();
if (value == this.getMin()) {
this.stackMin.pop();
}
return value;
}

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

public int getMin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}

/**
* 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();
*/

解答2[Java]:

核心思路

同样使用两个栈,不过压入逻辑相比解答1修改了一下。当要入栈的数字小于当前最小值的时候,把入栈的数字同时压入数据栈和最小值栈。当要入栈的数字大于等于当前最小值的时候,把当前最小值取出来再压入最小值栈一次,相当于当前的最小值是冗余的,但是冗余自有冗余的用处。

弹出元素的时候,不需要再进行检查,弹出元素的同时,也把最小值栈的元素弹出,因为最小值栈的元素是冗余的,就是为了一一对应,不用再检查。

代码

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
44
45
46
47
48
49
50
51
52
53
import java.util.ArrayDeque;
import java.util.Deque;

public class MinStack {
private Deque<Integer> stackData;
private Deque<Integer> stackMin;

/** initialize your data structure here. */
public MinStack() {
this.stackData = new ArrayDeque<>();
this.stackMin = new ArrayDeque<>();
}

public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum < this.getMin()) {
this.stackMin.push(newNum);
} else {
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}

public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
this.stackMin.pop();
return this.stackData.pop();
}

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

public int getMin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}

/**
* 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();
*/