Min Stack

problem

최솟값을 기억하는 stack을 구현하는 문제입니다.
https://leetcode.com/problems/min-stack

solution

//problem no: 155
class MinStack {
public:
    /** initialize your data structure here. */
    int minimum = INT_MAX;
    int numberOfEntries= 0;
    int* s;
    int capacity = 1;
    
    MinStack() {
        s = new int[capacity];
    }
    
    void push(int val) {
        if(numberOfEntries == capacity){
            capacity *= 2;
            int* tmp = new int[capacity];
            memcpy(tmp, s, sizeof(int) * numberOfEntries);
            swap(tmp, s);
            delete[] tmp;
        }
        s[numberOfEntries++] = val;
        minimum = val < minimum ? val : minimum;
    }
    
    void pop() {
        if(numberOfEntries == 1){
            minimum = INT_MAX;
        }else if(s[numberOfEntries-1] == minimum){
            minimum = s[0];
            for(int i=1;i<numberOfEntries-1;i++){
                minimum = min(s[i],minimum);
            }
        }
        numberOfEntries--;
    }
    
    int top() {
        return s[numberOfEntries-1];
    }
    
    int getMin() {
        return minimum;
    }
};

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

후기

min stack을 만드는데 stl stack을 쓰는건 반칙인것같아서
만들어보았습니다.

다 푼 후에 다른 사람들의 정답을 보았는데, 다 stl을 써서 쉽게 구현했더라구요. 생각해보니까 min stack과 stack이 다른점인 min만 구현하면 되는거였고, 굳이 안 쓸 필요가 없었던것 같습니다.

stack을 두개 써서 getMin을 O(1)로 구현하는게 핵심이었던것 같습니다.