Leetcode 155 (M)

Min Stack

처음 생각.

Finding the minimum element in a normal stack takes O(n)
to make it operates in O(1) -> additional space to store thing

Heap structures require O(1) time to get min element, but take O(logn) to insert.
시간에 대한 정렬과, 값에 대한 정렬된 상태가 필요함.

---

이 중 잘못된 생각.

1. priority queue의 insert는 Worst case에 O(n)이 걸릴지언정, random한 insert에 대한 average complexity는 O(1)이다.

2. 지우는 과정은 POP을 했을때만 나타난다. 즉, Min value를 트래킹하기 위해서 모든 value를 저장해 둘 필요는 없다.

First accepted code

class MinStack {
public:

    // getMin을 한다고 해서 min을 delete해야한다는 것은 아님.
    // 지울 수 있는건 어차피 삽입된 순서의 역순이고, 최소값이 어디있는가는 얼마나 지워졌냐에 달려있음.
    
    stack<int> stk;
    map<int, int> pq;
    
    MinStack() {

    }
    
    void push(int val) {
        stk.push(val);
        pq[val]++;
    }
    
    void pop() {
        int v = stk.top(); stk.pop();
        if(pq[v] == 1){
            pq.erase(v);
            return;
        }
        pq[v]--;
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return pq.begin()->first;
    }
};

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

Better code

class MinStack {
    stack<pair<int, int>> min_stack;
public:
    MinStack() {
        // Nothing
    }
    
    void push(int val) {
        int minimum;
        if (min_stack.empty()) {
            minimum = val;    
        } else {
            minimum = min(getMin(), val);
        }
        min_stack.push(pair(val, minimum));
    }
    
    void pop() {
        min_stack.pop();
    }
    
    int top() {
        return min_stack.top().first;
    }
    
    int getMin() {
        return min_stack.top().second;
    }
};

그냥 쌓아가면서, 해상 stack의 상태에서 top과 getMin시 얻어내야 하는 값을 둘 다 저장한다.

TIL

1. c++의 STL인 priority queue에는 find가 없다.
2. std::set을 pq를 대신해서 사용할 수 있지만, ket-value pair를 넣을 수는 없다.