716. Max Stack

Problem

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.

Thought Process

White Board

Below is the white board:

Code

class Solution:
    def isValid(self, s):
        st = []
        lefts = ["(", "{", "["]
        match = {
            ")":"(",
            "}":"{",
            "]":"["
        }

        if len(s) == 0:
            return True
        if len(s) == 1:
            return False


        for c in s:
            if c in lefts:
                st.append(c)
            else:
                if len(st) == 0:
                    return False
                if st.pop() != match[c]:
                    return False
        #important, need to check st is empty
        if len(st) == 0:
            return True
        else:
            return False

def test():
    s ="(("
    va = Solution().isValid(s)
    print(va)

test()    

True

Complexity

  • Time complexity is O(n*m)
  • used additional ds to creat stack

Optimization

Will try to figure out a recursive solution in the future.