【LeetCode】155. 해약하다

질문으로 연결

문제 개요

push(x) - 요소 xpush를 스택에 넣기

pop() - 스택의 상단에서 요소 제거

top() - 맨 위 요소 가져오기

getMin () - 스택의 최소 컴포넌트를 일정 시간에 반환

기능적인 창고를 설계하다.
예:

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

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

구속

-2^{31}\leq val\leq -2^{31} - 1

pop, getMin 방법은 반드시 비공식 창고에 호출해야 한다

최대 3\times10^4회 호출

생각

기본 창고 처리push,pop,top에 대해 솔직하게 실시하면 문제없을 것 같다.
단, getMin에 대해서는 상수 시간의 제한이 있다.
이 방법을 호출할 때 스택 전체를 탐색하는 실현 중 O(n)의 계산량이기 때문에 요건을 충족하지 못해 신경을 써야 한다는 것이다.
그럼 어떻게 실시하면 좋을까요?
스택의 이후 인라인 아웃(LIFO: Last In First Out) 구조는 데이터를 유지합니다.
따라서 push를 진행할 때 현재의 최소치m를 부가치x와 비교하여 비교적 작은 값을 유지하면 된다는 것을 알 수 있다.
또한 진행pop을 감안하면 유지(x, m)의 데이터를 통해 일정 시간getMin에 처리할 수 있음을 알 수 있다.
다음과 같은 생각으로 구현:

class MinStack(object):

    def __init__(self):
        self.data = []

    def push(self, x):
        if len(self.data) == 0:
            minVal = x
        else:
            minVal = min(self.getMin(), x)
        self.data = [(x, minVal)] + self.data

    def pop(self):
        self.data = self.data[1:]

    def top(self):
        return self.data[0][0]

    def getMin(self):
        return self.data[0][1]