Commit 0dd668f

@@ -5,18 +5,26 @@ end
 class MaxStack
   def initialize
     @items = []
+    @maxes = []
   end
 
   def push(value)
+    if @maxes.empty? || value > @maxes[-1]
+      @maxes.push(value)
+    end
     @items.push(value)
   end
 
   def pop
-    @items.pop
+    result = @items.pop
+    @maxes.pop if result == @maxes[-1]
+    result
   end
 
+  # time: O(1)
+  # space: O(1)
   def max
-    @items.max
+    @maxes[-1]
   end
 end