[PYTHON] Let Code Day 36 "155. Min Stack" starting from scratch

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 35 "160. Intersection of Two Linked Lists" starting from zero

Basically, I would like to solve the easy acceptance in descending order.

Twitter I'm doing it.

problem

The difficulty level is easy. This is the last question for easy in the Top 100 Liked Questions.

The problem is, implement the MinStack class with the push, pop, top and getMin functions.

The specifications of each function are as follows.

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.

Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

Output [null,null,null,null,-3,null,0,-2]

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

That is all for the usage example. I'm sure many programmers know about Stack, so I won't cover it here.

solution

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x: int) -> None:
        minElement = self.getMin()
        if minElement == None or x < minElement:
            minElement = x
        self.stack.append((x,minElement))

    def pop(self) -> None:
        self.stack.pop()
        

    def top(self) -> int:
        if len(self.stack) == 0:
            return None
        else:
            return self.stack[len(self.stack) - 1][0]

    def getMin(self) -> int:
        if len(self.stack) == 0:
            return None
        else:
            return self.stack[len(self.stack) - 1][1]
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
# Runtime: 72 ms, faster than 38.62% of Python3 online submissions for Min Stack.
# Memory Usage: 17.9 MB, less than 5.36% of Python3 online submissions for Min Stack.

I think slicing is convenient, but it seems that it will be implemented in a similar way in other languages as usual ... It's interesting to try implementing stack anyway, so I recommend writing it.

This time it looks like this. Thank you for your hard work.