[c++/LeetCode-Stack] 155. MinStack

 

 

 

 

난이도: Medium

키워드: Stack

 

 

문제

 

상수 시간 내에 push, pop, top 및 최소 요소를 검색하는 스택을 설계하십시오.

MinStack 클래스를 구현하십시오:

- MinStack()는 스택 객체를 초기화합니다.
- void push(int val)는 요소 val을 스택에 넣습니다.
- void pop()은 스택의 맨 위의 요소를 제거합니다.
- int top()은 스택의 맨 위 요소를 가져옵니다.
- int getMin()은 스택에서 최소 요소를 검색합니다.

각 함수에 대해 O(1) 시간 복잡도를 가진 솔루션을 구현해야 합니다.

 

문제 풀이

 

- O(1) 시간 내에 min 값을 반환하기 위해 추가 메모리를 써서 min 값을 반환할 수 있게 min_stack을 추가로  선언한다.

- min_stack 값에 지금까지의 min 값 과 현재 들어오는 값을 비교해서 해당 레벨에서의 min 값을 min_stack에 추가해준다.

 

* 참고로, erase는 iterator를 받아서 해당 iterator의 값을 삭제해주는 메소드

* 참고로, end() 는 iterator를 반환하지만, 맨 마지막 값을 가리키는 iterator가 아니라는 점에 유의하여야 한다.

 

class MinStack {
public:
    MinStack() {
        stack = {};
        min_stack = {};
    }
    
    void push(int val) {
        stack.emplace_back(val);
        if(min_stack.size())
            min_stack.emplace_back(min(val, min_stack.back()));
        else
            min_stack.emplace_back(val);
    }
    
    void pop() {
        stack.erase(stack.end()-1);
        min_stack.erase(min_stack.end()-1);
    }
    
    int top() {
        return stack.back();
    }
    
    int getMin() {
        return min_stack.back();
    }
private:
    vector<int> stack;
    vector<int> min_stack;
};

/**
 * 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();
 */