Repository navigation
Expand file tree
/
Copy pathMinStack.java
More file actions
76 lines (63 loc) · 1.76 KB
/
Copy pathMinStack.java
File metadata and controls
76 lines (63 loc) · 1.76 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
package DSA.Stack;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;
public class MinStack {
Stack<Integer> stack;
PriorityQueue<Integer> pq;
Set<Integer> deletedIds;
public MinStack() {
stack = new Stack<>();
pq = new PriorityQueue<>();
deletedIds = new HashSet<>();
}
public void push(int val) {
stack.push(val);
pq.add(val);
}
public void pop() {
cleanUpStack();
Integer pop = stack.pop();
deletedIds.add(pop);
}
public int top() {
cleanUpStack();
return stack.peek();
}
public int getMin() {
cleanUpHeap();
return pq.peek();
}
public void removeMin() {
cleanUpHeap();
if (!pq.isEmpty()) {
int removedVal = pq.poll();
deletedIds.add(removedVal);
}
}
private void cleanUpStack() {
while (!stack.isEmpty() && deletedIds.contains(stack.peek())) {
stack.pop();
}
}
private void cleanUpHeap() {
while (!pq.isEmpty() && deletedIds.contains(pq.peek())) {
pq.poll();
}
}
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(3);
minStack.push(5);
minStack.push(2);
minStack.push(1);
minStack.push(4);
System.out.println("Min: " + minStack.getMin()); // 1
minStack.removeMin(); // removes 1
System.out.println("Min after removeMin(): " + minStack.getMin()); // 2
minStack.pop(); // removes 4
System.out.println("Top: " + minStack.top()); // 1 (removed, should be 2)
System.out.println("Min now: " + minStack.getMin()); // 2
}
}