leetcode/java/716_Max_Stack.java at master · tonardo2015/leetcode · GitHub

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
classMaxStack {
TreeMap<Integer, List<Node>> map;
DoubleLinkedListdll;

publicMaxStack() {
map = newTreeMap();
dll = newDoubleLinkedList();
 }

publicvoidpush(intx) {
Nodenode = dll.add(x);
if(!map.containsKey(x))
map.put(x, newArrayList<Node>());
map.get(x).add(node);
 }

publicintpop() {
intval = dll.pop();
List<Node> L = map.get(val);
L.remove(L.size() - 1);
if (L.isEmpty()) map.remove(val);
returnval;
 }

publicinttop() {
returndll.peek();
 }

publicintpeekMax() {
returnmap.lastKey();
 }

publicintpopMax() {
intmax = peekMax();
List<Node> L = map.get(max);
Nodenode = L.remove(L.size() - 1);
dll.unlink(node);
if (L.isEmpty()) map.remove(max);
returnmax;
 }
}

classDoubleLinkedList {
Nodehead, tail;

publicDoubleLinkedList() {
head = newNode(0);
tail = newNode(0);
head.next = tail;
tail.prev = head;
 }

publicNodeadd(intval) {
Nodex = newNode(val);
x.next = tail;
x.prev = tail.prev;
tail.prev = tail.prev.next = x;
returnx;
 }

publicintpop() {
returnunlink(tail.prev).val;
 }

publicintpeek() {
returntail.prev.val;
 }

publicNodeunlink(Nodenode) {
node.prev.next = node.next;
node.next.prev = node.prev;
returnnode;
 }
}

classNode {
intval;
Nodeprev, next;
publicNode(intv) {val = v;}
}