added MinStack.java

FMZHOU · May 29, 2018 · a58514b · a58514b
1 parent c41d2e8
commit a58514b
Show file tree

Hide file tree

Showing 6 changed files with 330 additions and 0 deletions.
diff --git a/company/amazon/MinStack.java b/company/amazon/MinStack.java
@@ -0,0 +1,55 @@
+//Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
+//push(x) -- Push element x onto stack.
+//pop() -- Removes the element on top of the stack.
+//top() -- Get the top element.
+//getMin() -- Retrieve the minimum element in the stack.
+
+/**
+ * Your MinStack object will be instantiated and called as such:
+ * MinStack obj = new MinStack();
+ * obj.push(x);
+ * obj.pop();
+ * int param_3 = obj.top();
+ * int param_4 = obj.getMin();
+ */
+class MinStack {
+    class Node {
+        int data;
+        int min;
+        Node next;
+
+        public Node(int data, int min) {
+            this.data = data;
+            this.min = min;
+            this.next = null;
+        }
+    }
+    Node head;
+
+    /** initialize your data structure here. */
+    public MinStack() {
+
+    }
+
+    public void push(int x) {
+        if(head == null) {
+            head = new Node(x, x);
+        } else {
+            Node newNode = new Node(x, Math.min(x, head.min));
+            newNode.next = head;
+            head = newNode;
+        }
+    }
+
+    public void pop() {
+        head = head.next;
+    }
+
+    public int top() {
+        return head.data;
+    }
+
+    public int getMin() {
+        return head.min;
+    }
+}
diff --git a/company/bloomberg/MinStack.java b/company/bloomberg/MinStack.java
@@ -0,0 +1,55 @@
+//Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
+//push(x) -- Push element x onto stack.
+//pop() -- Removes the element on top of the stack.
+//top() -- Get the top element.
+//getMin() -- Retrieve the minimum element in the stack.
+
+/**
+ * Your MinStack object will be instantiated and called as such:
+ * MinStack obj = new MinStack();
+ * obj.push(x);
+ * obj.pop();
+ * int param_3 = obj.top();
+ * int param_4 = obj.getMin();
+ */
+class MinStack {
+    class Node {
+        int data;
+        int min;
+        Node next;
+
+        public Node(int data, int min) {
+            this.data = data;
+            this.min = min;
+            this.next = null;
+        }
+    }
+    Node head;
+
+    /** initialize your data structure here. */
+    public MinStack() {
+
+    }
+
+    public void push(int x) {
+        if(head == null) {
+            head = new Node(x, x);
+        } else {
+            Node newNode = new Node(x, Math.min(x, head.min));
+            newNode.next = head;
+            head = newNode;
+        }
+    }
+
+    public void pop() {
+        head = head.next;
+    }
+
+    public int top() {
+        return head.data;
+    }
+
+    public int getMin() {
+        return head.min;
+    }
+}
diff --git a/company/google/MinStack.java b/company/google/MinStack.java
@@ -0,0 +1,55 @@
+//Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
+//push(x) -- Push element x onto stack.
+//pop() -- Removes the element on top of the stack.
+//top() -- Get the top element.
+//getMin() -- Retrieve the minimum element in the stack.
+
+/**
+ * Your MinStack object will be instantiated and called as such:
+ * MinStack obj = new MinStack();
+ * obj.push(x);
+ * obj.pop();
+ * int param_3 = obj.top();
+ * int param_4 = obj.getMin();
+ */
+class MinStack {
+    class Node {
+        int data;
+        int min;
+        Node next;
+
+        public Node(int data, int min) {
+            this.data = data;
+            this.min = min;
+            this.next = null;
+        }
+    }
+    Node head;
+
+    /** initialize your data structure here. */
+    public MinStack() {
+
+    }
+
+    public void push(int x) {
+        if(head == null) {
+            head = new Node(x, x);
+        } else {
+            Node newNode = new Node(x, Math.min(x, head.min));
+            newNode.next = head;
+            head = newNode;
+        }
+    }
+
+    public void pop() {
+        head = head.next;
+    }
+
+    public int top() {
+        return head.data;
+    }
+
+    public int getMin() {
+        return head.min;
+    }
+}
diff --git a/company/snapchat/MinStack.java b/company/snapchat/MinStack.java
@@ -0,0 +1,55 @@
+//Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
+//push(x) -- Push element x onto stack.
+//pop() -- Removes the element on top of the stack.
+//top() -- Get the top element.
+//getMin() -- Retrieve the minimum element in the stack.
+
+/**
+ * Your MinStack object will be instantiated and called as such:
+ * MinStack obj = new MinStack();
+ * obj.push(x);
+ * obj.pop();
+ * int param_3 = obj.top();
+ * int param_4 = obj.getMin();
+ */
+class MinStack {
+    class Node {
+        int data;
+        int min;
+        Node next;
+
+        public Node(int data, int min) {
+            this.data = data;
+            this.min = min;
+            this.next = null;
+        }
+    }
+    Node head;
+
+    /** initialize your data structure here. */
+    public MinStack() {
+
+    }
+
+    public void push(int x) {
+        if(head == null) {
+            head = new Node(x, x);
+        } else {
+            Node newNode = new Node(x, Math.min(x, head.min));
+            newNode.next = head;
+            head = newNode;
+        }
+    }
+
+    public void pop() {
+        head = head.next;
+    }
+
+    public int top() {
+        return head.data;
+    }
+
+    public int getMin() {
+        return head.min;
+    }
+}
diff --git a/company/uber/MinStack.java b/company/uber/MinStack.java
@@ -0,0 +1,55 @@
+//Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
+//push(x) -- Push element x onto stack.
+//pop() -- Removes the element on top of the stack.
+//top() -- Get the top element.
+//getMin() -- Retrieve the minimum element in the stack.
+
+/**
+ * Your MinStack object will be instantiated and called as such:
+ * MinStack obj = new MinStack();
+ * obj.push(x);
+ * obj.pop();
+ * int param_3 = obj.top();
+ * int param_4 = obj.getMin();
+ */
+class MinStack {
+    class Node {
+        int data;
+        int min;
+        Node next;
+
+        public Node(int data, int min) {
+            this.data = data;
+            this.min = min;
+            this.next = null;
+        }
+    }
+    Node head;
+
+    /** initialize your data structure here. */
+    public MinStack() {
+
+    }
+
+    public void push(int x) {
+        if(head == null) {
+            head = new Node(x, x);
+        } else {
+            Node newNode = new Node(x, Math.min(x, head.min));
+            newNode.next = head;
+            head = newNode;
+        }
+    }
+
+    public void pop() {
+        head = head.next;
+    }
+
+    public int top() {
+        return head.data;
+    }
+
+    public int getMin() {
+        return head.min;
+    }
+}
diff --git a/leetcode/design/MinStack.java b/leetcode/design/MinStack.java
@@ -0,0 +1,55 @@
+//Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
+//push(x) -- Push element x onto stack.
+//pop() -- Removes the element on top of the stack.
+//top() -- Get the top element.
+//getMin() -- Retrieve the minimum element in the stack.
+
+/**
+ * Your MinStack object will be instantiated and called as such:
+ * MinStack obj = new MinStack();
+ * obj.push(x);
+ * obj.pop();
+ * int param_3 = obj.top();
+ * int param_4 = obj.getMin();
+ */
+class MinStack {
+    class Node {
+        int data;
+        int min;
+        Node next;
+
+        public Node(int data, int min) {
+            this.data = data;
+            this.min = min;
+            this.next = null;
+        }
+    }
+    Node head;
+
+    /** initialize your data structure here. */
+    public MinStack() {
+
+    }
+
+    public void push(int x) {
+        if(head == null) {
+            head = new Node(x, x);
+        } else {
+            Node newNode = new Node(x, Math.min(x, head.min));
+            newNode.next = head;
+            head = newNode;
+        }
+    }
+
+    public void pop() {
+        head = head.next;
+    }
+
+    public int top() {
+        return head.data;
+    }
+
+    public int getMin() {
+        return head.min;
+    }
+}