FilesExpand file tree

 master

/

716_Max_Stack.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

80 lines (67 loc) · 1.59 KB

 master

/

716_Max_Stack.java

Copy path

Top

File metadata and controls

• Code
• Blame

80 lines (67 loc) · 1.59 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

class MaxStack {

TreeMap<Integer, List<Node>> map;

DoubleLinkedList dll;

public MaxStack() {

map = new TreeMap();

dll = new DoubleLinkedList();

}

public void push(int x) {

Node node = dll.add(x);

if(!map.containsKey(x))

map.put(x, new ArrayList<Node>());

map.get(x).add(node);

}

public int pop() {

int val = dll.pop();

List<Node> L = map.get(val);

L.remove(L.size() - 1);

if (L.isEmpty()) map.remove(val);

return val;

}

public int top() {

return dll.peek();

}

public int peekMax() {

return map.lastKey();

}

public int popMax() {

int max = peekMax();

List<Node> L = map.get(max);

Node node = L.remove(L.size() - 1);

dll.unlink(node);

if (L.isEmpty()) map.remove(max);

return max;

}

}

class DoubleLinkedList {

Node head, tail;

public DoubleLinkedList() {

head = new Node(0);

tail = new Node(0);

head.next = tail;

tail.prev = head;

}

public Node add(int val) {

Node x = new Node(val);

x.next = tail;

x.prev = tail.prev;

tail.prev = tail.prev.next = x;

return x;

}

public int pop() {

return unlink(tail.prev).val;

}

public int peek() {

return tail.prev.val;

}

public Node unlink(Node node) {

node.prev.next = node.next;

node.next.prev = node.prev;

return node;

}

}

class Node {

int val;

Node prev, next;

public Node(int v) {val = v;}

}