LeetCode : 155. Min Stack

문제 링크

문제 먼저 읽기

• 푸시, 팝, 탑, 최소 요소 검색을 일정 시간 내에 지원하는 스택을 구현하시오.

어떻게 풀까?

생각

• ArrayList 혹은 int[]로 구현해볼 수 있다.

수도코드

class MinStack {
    private List<Integer> stack;
    private List<Integer> minStack; // 최소값 저장 스택

    public MinStack() { // 스택 초기화
        this.stack = new ArrayList<>();
        this.minStack = new ArrayList<>();
    }
    
    public void push(int val) {
        if (stack.size() == 0) { // 첫요소일 때. 처음에 이부분을 생각하지 못해서 emptyStackException이 발생했었다.
            this.minStack.add(val);
        } else {
            this.minStack.add(Math.min(val, minStack.get(minStack.size()-1)));
        }
        this.stack.add(val);
    }
    
    public void pop() {
        this.stack.remove(stack.size() -1);
        this.minStack.remove(minStack.size() -1);
    }
    
    public int top() {
        return stack.get(stack.size() -1);
    }
    
    public int getMin() {
        return minStack.get(minStack.size() -1);
    }
}

결과

<aside> 💡 Success

Runtime: 4 ms, faster than 99.18% of Java online submissions for Min Stack.

Memory Usage: 47.1 MB, less than 63.82% of Java online submissions for Min Stack.

</aside>

다른 풀이 방식과 문제 회고

• linked list처럼 구현한 사례가 있었다.
• stack도 어차피 탐색에 시간 복잡도가 높은 편이라 이렇게 구현하는 것이 테스트 통과에 효율적인 것 같다.

class MinStack {
    Node head;
    class Node {
        int min;
        int val;
        Node next;

        Node(int min, int val, Node next) {
            this.min = min;
            this.val = val;
            this.next = next;
        }
    }
    public MinStack() {
        head = null;
    }
    
    public void push(int val) {
        int min = (head==null) ? val : head.min;
        Node newNode = new Node(Math.min(min, val), val, head);
        head = newNode;
    }
    
    public void pop() {
        if (head.next == null || head == null) {
            head = null;
            return;
        }

        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.min;
    }
}