155. Min Stack

155. Min Stack

---

문제

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.

문제 사이트

Example 1:

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

Constraints:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

---

문제 해석

• Stack의 논리를 직접 구현해보는 문제
• getMin() 함수는 stack에 들어있는 숫자 중 최소를 리턴하는 함수
• 면접에서 이것을 물어본다면 STL stack 문법을 사용하지 않고 구현해야할 것이다.
• 시간복잡도 O(1) 로 구현해보라는데 토론과 해석을 본 결과 문제 오류라고 한다.

---

구현

class MinStack {
public:
    vector<vector<int>> v_stk;

    MinStack() {
        
    }
    
    void push(int val) {
        if(v_stk.empty())
        {
            v_stk.push_back({val, val});
        }    
        else
        {
            v_stk.push_back({val, min(v_stk.back()[1], val)});
        }
    }
    
    void pop() {
        v_stk.pop_back();
    }
    
    int top() {
        return v_stk.back()[0];
    }
    
    int getMin() {
        return v_stk.back()[1];
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

---

코드 해설

vector<vector<int>> v_stk;

• vector를 이용해 stack을 구현한다.
• 최소값도 출력해야하기 때문에 vector 안의 vector 로 선언한다.

else
{
    v_stk.push_back({val, min(v_stk.back()[1], val)});
}

• val 은 넣는 값, 그 뒤는 최솟값을 계산하기 위해 min으로 최솟값 계산

• leetcode
• coding-test
• stack
• medium