ゼロから始めるLeetCode Day36「155. Min Stack」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day35「160. Intersection of Two Linked Lists」
次回
ゼロから始めるLeetCode Day37「105. Construct Binary Tree from Preorder and Inorder Traversal」

問題

難易度はeasy。
Top 100 Liked Questionsのeasyはこれが最後の問題になります。

問題としては、push,pop,top,getMinという関数を持つMinStackクラスを実装してくださいというものです。

なお、それぞれの関数の仕様は以下の通り。

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

使用例は以上です。
Stackについては多くのプログラマーが知っていると思うのでここでは触れません。

解法

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.

スライスが便利、かと思いきや普通に他の言語でも普通に似たような実装になりそうですね・・・
何にせよstackを実装してみるのは面白いので書いてみることをお勧めします。

今回はこんな感じで。お疲れ様でした。