# Leetcode MaxStack in Python

My solution to Leetcode MaxStack in python in Python. I have two solution one is using linked-list and another one is using list.

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.

Using list:

class MaxStack_list:
def __init__(self):
"""
"""
self.max_val = None

def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""

def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""

def top(self):
"""
Get the top element.
:rtype: int
"""

def peekMax(self):
"""
Retrieve the maximum element in the stack.
:rtype: int
"""
return self.max_val

def popMax(self):
"""
Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
:rtype: void
"""
v = self.max_val
return v


class Node:
def __init__(self, x):
self.val = x
self.next = None

class MaxStack:
def __init__(self):
"""
"""
self.max_val = None

def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
n = Node(x)
else:
self.max_val = max(x, self.max_val) if self.max_val or self.max_val == 0 else x

def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
rtn = None

self.max_val = v
return rtn

def top(self):
"""
Get the top element.
:rtype: int
"""

def peekMax(self):
"""
Retrieve the maximum element in the stack.
:rtype: int
"""
return self.max_val

def popMax(self):
"""
Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
:rtype: void
"""
while cur:
if cur.val == self.max_val and cur == self.head:
break
elif cur.val == self.max_val:
prev.next = cur.next
break

prev, cur = cur, cur.next

tmp = self.max_val
v = cur.val if cur else None
while cur:
if cur:
v = max(v, cur.val)
cur = cur.next
self.max_val = v
return tmp


The return type for popMax should be int not void.

When you push a new item, your max can only increase above the current maximum. So instead of

self.max_val = max(max(self.head), x)


which is $$\O(n)\$$, you should have

self.max_val = max(self.max_val, x)


which is $$\O(1)\$$.

Theif self.max_val or self.max_val == 0 condition is better written as if self.max_val is not None.