[2주차] 155. Min Stack

https://leetcode.com/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150 

Min Stack - LeetCode

---

📝 문제

push, pop, top 기능과 상수 시간에 현재 스텍의 원소중 최소값을 리턴하는 스택을 설계하라.

 

🎈 풀이

강의때 배웠던 내용을 복습하는 문제이다.

일반적으로 스택은 min 값을 찾기 위해선 O(n) 시간의 선형탐색을 진행해야 하기 때문에 일반적인 스택과는 다른 구조가 필요하다.

Methods pop, top and getMin operations will always be called on non-empty stacks. 라는 조건이 존재하므로 예외처리는 하지 않았다.

class MinStack {
    
    Node top;

    public void push(int val) {
        Node newNode = new Node(val);
        if (top == null) {
            newNode.min = val;
        } else {
            newNode.min = Math.min(top.min, val);
            newNode.next = top;
        }
        top = newNode;
    }
    
    public void pop() { top = top.next; }
    
    public int top() { return top.val; }
    
    public int getMin() { return top.min; }

    private class Node {
        int val;
        int min;
        Node next;

        Node(int val) { this.val = val; }
    }
}

 

• Stack 에 원소를 저장할 때, 값을 그대로 저장하는 것이 아닌 Node를 사용한다.
• Node의 val은 값, min 은 현재 스택 상태에서의 최솟값, next는 다음 연결된 원소이다.
• push 할 때, Stack 에 이미 원소가 존재한다면, 현재 top의 min 값을 가져와서 push 하려는 newNode 와 비교한다.
  • newNode.val 과 top.min 값중 작은 값을 newNode.min 에 저장한다.
  • 그 외 다른 원소의 값은 변경하지 않는다.

이렇게 설계하면 top.min 은 항상 현재 남은 원소에서의 최솟값을 가지게 된다.