Repository navigation
Expand file tree
/
Copy pathMinStackWithDuplicates.java
More file actions
94 lines (78 loc) · 2.32 KB
/
Copy pathMinStackWithDuplicates.java
File metadata and controls
94 lines (78 loc) · 2.32 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
package DSA.Stack;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
public class MinStackWithDuplicates {
private static class Node {
int val;
int id; // unique id to sync between stack and heap
Node(int val, int id) {
this.val = val;
this.id = id;
}
}
MyStack<Node> stack;
PriorityQueue<Node> minHeap;
Set<Integer> deletedIds;
int counter;
public MinStackWithDuplicates() {
stack = new MyStack<>();
deletedIds = new HashSet<>();
counter = 0;
minHeap = new PriorityQueue<>((a, b) -> {
if (a.val != b.val) return Integer.compare(a.val, b.val);
return Integer.compare(a.id, b.id);
});
}
public void push(int val) {
Node node = new Node(val, counter++);
stack.push(node);
minHeap.offer(node);
}
public void pop() {
cleanUpStack();
if (!stack.isEmpty()) {
Node node = stack.pop();
deletedIds.add(node.id);
}
}
public int top() {
cleanUpStack();
return stack.peek().val;
}
public int getMin() {
cleanUpHeap();
return minHeap.peek().val;
}
public void removeMin() {
cleanUpHeap();
if (!minHeap.isEmpty()) {
Node min = minHeap.poll();
deletedIds.add(min.id);
}
}
private void cleanUpStack() {
while (!stack.isEmpty() && deletedIds.contains(stack.peek().id)) {
stack.pop();
}
}
private void cleanUpHeap() {
while (!minHeap.isEmpty() && deletedIds.contains(minHeap.peek().id)) {
minHeap.poll();
}
}
public static void main(String[] args) {
MinStackWithDuplicates minStack = new MinStackWithDuplicates();
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
}
}