Min Stack

Min Stack

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

문제

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.

풀이

1. stack에는 {삽입할 값, 현재까지의 최솟값} 형태로 저장한다.
2. 최솟값은 push, pop할 때 갱신되도록 한다.
3. push할 때, 지금 삽입할 값과 현재까지의 최솟값을 비교해서 minVal을 넣는다.
4. pop할 때, 스택에 하나이상이 남아있다면 그 값의 최솟값을 대체, 없다면 Integer Max Value로 갱신

수도 코드

stack = []
minVal = 2^31

push(x):
	minVal = min(minVal, x)
    stack에 (x, minVal)을 추가한다

pop():
	x, minX = stack.pop()
    minVal = 스택이 비어있다면 ? Integer.MAX_VALUE : stack.top()[1]

top():
	return stack.top()[0]

getMin():
	return stack.top()[1]

Solution(Runtime: 5ms)

import java.util.*;


class MinStack {

    private Stack<int[]> storage;

    private int minVal;

    public MinStack() {
        storage = new Stack<>();
        minVal = Integer.MAX_VALUE;
    }
    
    public void push(int val) {
        minVal = Math.min(minVal, val);
        storage.add(new int[] {val, minVal});
    }
    
    public void pop() {
        int[] deleted = storage.pop();
        minVal = (!storage.isEmpty()) ? storage.peek()[1] : Integer.MAX_VALUE;
    }
    
    public int top() {
        return storage.peek()[0];
    }
    
    public int getMin() {
        return storage.peek()[1];
    }
}

나는 현재를 기준으로 최솟값도 같이 저장했다. 사실 처음에는 우선순위큐를 별도로 둬서 최솟값을 가져오려고 했지만, [5, 3, 4]와 같은 경우 4의 값은 계속 우선순위 큐에 남아있게 되어 처리가 어렵게 되었다.

다른 사람의 풀이는 두개의 스택을 두거나 스택에 value와 min 값을 두번 추가하는 방식이 있었다. 두번 추가하는 방식은 만약 내 실수로 한번 pop하게 된다면? 같은 타입이라서 컴파일에러도 발생하지 않을 것이며 실수 방지를 위해서 연산을 하나로 묶는 것이 좋을 것 같다!