refactor 716

fishercoder1534 · fishercoder1534 · commit b1f90b7dcb91 · 2020-07-22T12:41:10.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_716.java b/src/main/java/com/fishercoder/solutions/_716.java
@@ -6,38 +6,13 @@
 import java.util.Stack;
 import java.util.TreeMap;
 
-/**
- * 716. Max Stack
- *
- * Design a max stack that supports push, pop, top, peekMax and popMax.
- *
- push(x) -- Push element x onto stack.
- pop() -- Remove the element on top of the stack and return it.
- top() -- Get the element on the top.
- peekMax() -- Retrieve the maximum element in the stack.
- popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
-
- Example 1:
- MaxStack stack = new MaxStack();
- stack.push(5);
- stack.push(1);
- stack.push(5);
- stack.top(); -> 5
- stack.popMax(); -> 5
- stack.top(); -> 1
- stack.peekMax(); -> 5
- stack.pop(); -> 1
- stack.top(); -> 5
- Note:
- -1e7 <= x <= 1e7
- Number of operations won't exceed 10000.
- The last four operations won't be called when stack is empty.
- */
 public class _716 {
     public static class Solution1 {
-      /**This is O(n) for popMax() and pop() while O(1) for the other three operations which is UN-acceptable during an interview!
-       * We need to do better than O(n) time complexity in order to ace the interview!
-       * But O(1) is impossible, so let's aim for O(logn).*/
+        /**
+         * This is O(n) for popMax() and pop() while O(1) for the other three operations which is UN-acceptable during an interview!
+         * We need to do better than O(n) time complexity in order to ace the interview!
+         * But O(1) is impossible, so let's aim for O(logn).
+         */
         public static class MaxStack {
 
             private int max;
@@ -110,106 +85,110 @@ public int popMax() {
         }
     }
 
-  public static class Solution2 {
-    /** Use a treemap and a doubly linked list to achieve O(logn) time complexity. */
+    public static class Solution2 {
+        /**
+         * Use a treemap and a doubly linked list to achieve O(logn) time complexity.
+         */
 
-    static class Node {
-      int val;
-      Node prev;
-      Node next;
+        static class Node {
+            int val;
+            Node prev;
+            Node next;
 
-      public Node(int val) {
-        this.val = val;
-      }
-    }
+            public Node(int val) {
+                this.val = val;
+            }
+        }
 
-    static class DoublyLinkedList {
-      Node head;
-      Node tail;
-
-      public DoublyLinkedList() {
-        head = new Node(0);
-        tail = new Node(0);
-        head.next = tail;
-        tail.prev = head;
-      }
-
-      public Node add(int val) {
-        /**For this doubly linked list, we always add it to the end of the list*/
-        Node x = new Node(val);
-        x.next = tail;
-        x.prev = tail.prev;
-        tail.prev.next = x;
-        tail.prev = tail.prev.next;
-        return x;
-      }
-
-      public int pop() {
-        /**for pop(), we always pop one from the tail of the doubly linked list*/
-        return unlink(tail.prev).val;
-      }
-
-      public Node unlink(Node node) {
-        node.prev.next = node.next;
-        node.next.prev = node.prev;
-        return node;
-      }
-
-      public int peek() {
-        return tail.prev.val;
-      }
-    }
+        static class DoublyLinkedList {
+            Node head;
+            Node tail;
 
-    public static class MaxStack {
-      TreeMap<Integer, List<Node>> treeMap;
-      /**
-       * the reason we have a list of nodes as treemap's value is because one value could be pushed
-       * multiple times into this MaxStack and we want to keep track of all of them.
-       */
-      DoublyLinkedList doublyLinkedList;
-
-      /** initialize your data structure here. */
-      public MaxStack() {
-        treeMap = new TreeMap();
-        doublyLinkedList = new DoublyLinkedList();
-      }
-
-      public void push(int x) {
-        Node node = doublyLinkedList.add(x);
-        if (!treeMap.containsKey(x)) {
-          treeMap.put(x, new ArrayList<>());
-        }
-        treeMap.get(x).add(node);
-      }
-
-      public int pop() {
-        int val = doublyLinkedList.pop();
-        List<Node> nodes = treeMap.get(val);
-        nodes.remove(nodes.size() - 1);
-        if (nodes.isEmpty()) {
-          treeMap.remove(val);
+            public DoublyLinkedList() {
+                head = new Node(0);
+                tail = new Node(0);
+                head.next = tail;
+                tail.prev = head;
+            }
+
+            public Node add(int val) {
+                /**For this doubly linked list, we always add it to the end of the list*/
+                Node x = new Node(val);
+                x.next = tail;
+                x.prev = tail.prev;
+                tail.prev.next = x;
+                tail.prev = tail.prev.next;
+                return x;
+            }
+
+            public int pop() {
+                /**for pop(), we always pop one from the tail of the doubly linked list*/
+                return unlink(tail.prev).val;
+            }
+
+            public Node unlink(Node node) {
+                node.prev.next = node.next;
+                node.next.prev = node.prev;
+                return node;
+            }
+
+            public int peek() {
+                return tail.prev.val;
+            }
         }
-        return val;
-      }
-
-      public int top() {
-        return doublyLinkedList.peek();
-      }
-
-      public int peekMax() {
-        return treeMap.lastKey();
-      }
-
-      public int popMax() {
-        int max = treeMap.lastKey();
-        List<Node> nodes = treeMap.get(max);
-        Node node = nodes.remove(nodes.size() - 1);
-        doublyLinkedList.unlink(node);
-        if (nodes.isEmpty()) {
-          treeMap.remove(max);
+
+        public static class MaxStack {
+            TreeMap<Integer, List<Node>> treeMap;
+            /**
+             * the reason we have a list of nodes as treemap's value is because one value could be pushed
+             * multiple times into this MaxStack and we want to keep track of all of them.
+             */
+            DoublyLinkedList doublyLinkedList;
+
+            /**
+             * initialize your data structure here.
+             */
+            public MaxStack() {
+                treeMap = new TreeMap();
+                doublyLinkedList = new DoublyLinkedList();
+            }
+
+            public void push(int x) {
+                Node node = doublyLinkedList.add(x);
+                if (!treeMap.containsKey(x)) {
+                    treeMap.put(x, new ArrayList<>());
+                }
+                treeMap.get(x).add(node);
+            }
+
+            public int pop() {
+                int val = doublyLinkedList.pop();
+                List<Node> nodes = treeMap.get(val);
+                nodes.remove(nodes.size() - 1);
+                if (nodes.isEmpty()) {
+                    treeMap.remove(val);
+                }
+                return val;
+            }
+
+            public int top() {
+                return doublyLinkedList.peek();
+            }
+
+            public int peekMax() {
+                return treeMap.lastKey();
+            }
+
+            public int popMax() {
+                int max = treeMap.lastKey();
+                List<Node> nodes = treeMap.get(max);
+                Node node = nodes.remove(nodes.size() - 1);
+                doublyLinkedList.unlink(node);
+                if (nodes.isEmpty()) {
+                    treeMap.remove(max);
+                }
+                return max;
+            }
         }
-        return max;
-      }
     }
-  }
 }
