blob: dc27bc78d9752ae740318d45e710553412adfaf8 (
plain)
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
|
def assert_equal(x, y)
raise [x, y].inspect unless x == y
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
result = @items.pop
@maxes.pop if result == @maxes[-1]
result
end
# time: O(1)
# space: O(1)
def max
@maxes[-1]
end
end
stack = MaxStack.new
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(2)
assert_equal 3, stack.max
stack.pop
stack.pop
assert_equal 2, stack.max
puts 'Yay!'
|
