Min Stack[Stack,Design]

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

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.

일단 뭐,, 문제 이해는 쉽다.

일단 그냥 self 부분에 list나 deque같은 거 만들어 놓고 거기다가 첨가 하는 방식으로 하면 안 되나..?

하는 Naive한 생각이 든다.

 

 

1. Python

해당 Naive한 방법을 실행에 옮기기로 함

class MinStack:

    def __init__(self):
        # list를 만들면 되지 않나?
        self.s = deque()

    def push(self, val: int) -> None:
        self.s.append(val)
        return
    def pop(self) -> None:
        if self.s : self.s.pop()
        else : return
    def top(self) -> int:
        if self.s : return self.s[-1]
        else : return
    def getMin(self) -> int:
        if self.s : return min(self.s)
        else : return

 

뭐.. pass는 했는데 좀 찝찝하다.

Accepted graph 상에서도 거의 문 닫고 들어온 판국이다.

 

 

 

2. C++

이번엔 Linked List로 만들어보고 싶었다.

 

Linked List를 쓰려면 이렇게 Node에 대해서 struct를 만들어줘야 한다.

각 Node의 initialize는 Node 정의하는 Bracket 안에다가 해주면 된다.

여기선 기존 Stack과는 다르게 min value를 tracking 하는 것이 관건이었는데, int getmin()을 할 때, 그제서야 각 Node를 순회하며 min value를 찾는 것은 time complexity가 O(N)이 걸리므로 부적절했다.(문제에선 O(1)을 요구했기 때문)

 

그래서 각 Node별로 그 Node가 생기는 시점까지의 Min_value를 attribute로 만들어줘서 관리를 해주었더니 깔끔!

 

class MinStack {
public:
    struct Node{
        int val;
        int min_val;
        Node* next;
        Node(int a):val(a),next(nullptr),min_val(0){}
    };
    Node* head;
    // How can we keep tracking min_val...
    int size;
    MinStack(){
        head = nullptr;
        size = 0;
    }
    void push(int val){
        Node* new_node = new Node(val);
        if(!head){
            head = new_node;
            new_node->min_val = val;
        }
        else{
            new_node -> next = head;
            int min_temp = min(val,head->min_val);
            head = new_node;
            head->min_val = min_temp;
        }
        size++;
    }
    
    void pop() {
        if(size==0) return;
        Node* temp = head;
        head = head->next;
        delete temp;
        size--;
    }
    
    int top() {
        if(size==0) return NULL;
        else return head->val;
    }
    int getMin() {
        if(!head) return NULL;
        else return head->min_val;
    }
};

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