Repository navigation
Expand file tree
/
Copy pathL155_MinStack.java
More file actions
115 lines (101 loc) · 2.63 KB
/
Copy pathL155_MinStack.java
File metadata and controls
115 lines (101 loc) · 2.63 KB
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package LeetCode;
import java.util.LinkedList;
import java.util.Stack;
/**
* 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();
*/
public class L155_MinStack {
/* private LinkedList<Integer> stack=null;
int min=Integer.MAX_VALUE;
public L155_MinStack() {
stack=new LinkedList<Integer>();
}
public void push(int x) {
if(x<=min){
stack.addLast(min);//把之前的min压栈
min=x;
}
stack.addLast(x);
}
public void pop() {
if(min==stack.removeLast())
min=stack.removeLast();
}
public int top() {
return stack.getLast();
}
public int getMin() {
return min;
}*/
//数组实现
/*实时改变min
Runtime: 76 ms, faster than 46.13% of Java online submissions for Min Stack.
*/
/* private Integer[] stack=null;
private int maxSize=10000;
private int top=-1;
int min=Integer.MAX_VALUE;
public L155_MinStack() {
stack=new Integer[maxSize];
}
public void push(int x) {
if(top==maxSize-1){//栈满
maxSize*=2;
Integer[] temp=stack;
stack=new Integer[maxSize];
for(int i=0;i<temp.length;i++){
stack[i]=temp[i];
}
}
stack[++top]=x;
if(stack[top]<min)
min=stack[top];
}
public void pop() {
if(stack[top]==min){
min=Integer.MAX_VALUE;
for(int i=0;i<top;i++)
{
if(stack[i]<min)
min=stack[i];
}
}
top--;
}
public int top() {
return stack[top];
}
public int getMin() {
return min;
}*/
/*注意最小值的保存，否则后边没法求min
使用java的stack
*/
private Stack<Integer> stack=null;
int min=Integer.MAX_VALUE;
public L155_MinStack() {
stack=new Stack<Integer>();
}
public void push(int x) {//int比Integer快好多啊
if(x<=min){
stack.push(min);//把之前的min压栈
min=x;
}
stack.push(x);
}
public void pop() {
if(min==stack.pop())//当前栈顶数字等于最小值，栈顶出栈，最小数字为下方数字，栈顶入栈前的最小数字。不管等不等，pop操作都执行过了
min=stack.pop();//把最小值出栈，余下正常栈顶
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}