[stack][Medium] 155. Min Stack

https://leetcode.com/problems/min-stack/description/

 

Min stack을 구현하라. 

모든 stack function은 O(1)에 작동하여야 한다.

 

 

두개의 stack을 사용한다. 

하나는 기본 stack의 용도로, 

다음 stack은 최소값 buffer로 사용한다. 

 

stack의 본질은 어떤 특정 data를 넣은 역순으로 꺼내는 것이다. 

최소값 stack에 (input 당시에) 최소값을 넣으면 꺼낼 때도 역시 보장되는 것이다.

그냥 변수 하나를 써서 최소값을 기억해 놓는다고 생각해 보자. 

하나에 대해서는 잘 작동할 것이나, 이것을 반환한 이후에 그 이전 최소값 정보가 필요하게 되고, 

이것의 기능을 하는 것 또한 stack이 적당한 것이다. 

 

코드 

class MinStack 
{
    stack<int> mMainStack;
    stack<int> mMinStack;
public:
    MinStack() 
    {}

    void push(int val)
    {
        mMainStack.push(val);
        if (mMinStack.size()==0 || (mMinStack.size()>0 && mMinStack.top()>=val))
            mMinStack.push(val);
    }
    void pop()
    {
        if (mMainStack.size() == 0)
            return;

        int val = mMainStack.top();
        mMainStack.pop();

        if (mMinStack.size()>0 && val==mMinStack.top())
            mMinStack.pop();
    }
    int top()
    {
        return mMainStack.top();
    }
    int getMin()
    {
        return mMinStack.top();
    }
};

 

 

결과.