add a solution for 155

fishercoder1534 · fishercoder1534 · commit 4c640c0f4491 · 2021-10-25T07:49:46.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_155.java b/src/main/java/com/fishercoder/solutions/_155.java
@@ -1,37 +1,16 @@
 package com.fishercoder.solutions;
 
+import java.util.Deque;
+import java.util.LinkedList;
 import java.util.Stack;
 
-/**
- * 155. Min Stack
- * 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.
-
- * Example:
- * MinStack minStack = new MinStack();
- * minStack.push(-2);
- * minStack.push(0);
- * minStack.push(-3);
- * minStack.getMin();   --> Returns -3.
- * minStack.pop();
- * minStack.top();      --> Returns 0.
- * minStack.getMin();   --> Returns -2.
- */
-
 public class _155 {
 
     public static class Solution1 {
         class MinStack {
             private Stack<Integer> stack;
             private int min;
 
-            /**
-             * initialize your data structure here.
-             */
             public MinStack() {
                 stack = new Stack();
                 min = Integer.MAX_VALUE;
@@ -64,4 +43,45 @@ public int getMin() {
             }
         }
     }
+
+    public static class Solution2 {
+        /**
+         * We could store a pair onto the stack: the first element in the pair is the value itself,
+         * the second element in the pair is the current minimum element so far seen on the stack.
+         */
+        class MinStack {
+            Deque<int[]> stack;
+
+            public MinStack() {
+                stack = new LinkedList<>();
+            }
+
+            public void push(int val) {
+                if (!stack.isEmpty()) {
+                    int[] last = stack.peekLast();
+                    int currentMin = last[1];
+                    if (val < currentMin) {
+                        stack.addLast(new int[]{val, val});
+                    } else {
+                        stack.addLast(new int[]{val, currentMin});
+                    }
+                } else {
+                    stack.addLast(new int[]{val, val});
+                }
+            }
+
+            public void pop() {
+                stack.pollLast();
+            }
+
+            public int top() {
+                return stack.peekLast()[0];
+            }
+
+            public int getMin() {
+                return stack.peekLast()[1];
+            }
+        }
+
+    }
 }
