[알고리즘] LeetCode - Min Stack

Min Stack - LeetCode

문제 설명

• push, pop, top 반환, stack에서의 최솟값 반환을 지원하는 스택을 설계해야 한다.
• 기능에 해당하는 로직을 구현해야 한다.

문제 해결

• 별도의 Nodo에 val과 push 시점에서의 최솟값인 min을 저장할 클래스를 선언한다.
• Node 클래스를 통해 push시 모든 리스트를 순환하여 찾을 필요가 없다.

시간 복잡도

• O(1) : 최솟값을 찾을 때
• top 위치의 최솟값이 현재 stack에서의 최솟값이기 떄문에 O(1)의 시간복잡도로 최솟값을 찾을 수 있다.

풀이 코드

import java.util.*;

class MinStack {
    static class Node {
        int val;
        int min;
        public Node (int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    private List<Node> stack;
    private int top;

    public MinStack() {
        stack = new ArrayList<>();
        top = -1;        
    }
    
    public void push(int val) {
        int min;
        if (top == -1) {
            min = val;
        } else {
            min = stack.get(top).min;
            min = Math.min(min, val);
        }

        stack.add(new Node(val, min));
        top++;
    }
    
    public void pop() {
        stack.remove(top--);
    }
    
    public int top() {
        return stack.get(top).val;       
    }
    
    public int getMin() {
        return stack.get(top).min;
    }
}

결과

시간	메모리
4 ms	47 MB