题目：
题解：
1、解法一：最笨方法，遍历栈实现（时间复杂度O(n)）
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
| class MinStack {
Stack<Integer> stack = null;
public MinStack() {
stack = new Stack<Integer>();
}
public void push(int x) {
stack.push(x);
}
public void pop() {
if (!stack.empty()){
stack.pop();
}
}
public int top() {
int peek = (int) stack.peek();
return peek;
}
public int min() {
if (!stack.empty()){
int min = stack.peek();
for (Integer x : stack) {
if (x < min) {
min = x;
}
}
return min;
}else {
return 0;
}
}
}
|
2、解法二：多加一个栈，时间复杂度从O(n)变到O(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
| class MinStack {
Stack<Integer> stack1= null;
Stack<Integer> stack2 = null;
public MinStack() {
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
}
public void push(int x) {
stack1.push(x);
if (stack2.empty() || stack2.peek() >= x) {
stack2.push(x);
}
}
public void pop() {
if (!stack1.empty()){
if (stack1.peek().equals(stack2.peek())){
stack2.pop();
}
stack1.pop();
}
}
public int top() {
int peek = (int) stack1.peek();
return peek;
}
public int min() {
if (!stack1.empty()){
return stack2.peek();
}else {
return 0;
}
}
}
|