LeetCode 155: 이전 최솟값을 함께 저장하는 Min Stack
최솟값을 꺼낸 다음이 문제였습니다
push, pop, top과 함께 최솟값을 조회하는 getMin을 구현하는 문제입니다. 기본 연산은 자바의 스택을 사용하려 했지만 최솟값 관리가 남았습니다.
현재 최솟값만 변수에 저장하면 그 값을 pop했을 때 다음 최솟값을 알 수 없습니다. 그래서 새 최솟값을 넣기 전에 이전 최솟값도 스택에 저장했습니다.
val <= minValue이면 먼저 이전 minValue를 넣고, 최솟값을 val로 바꾼 뒤 실제 값을 넣습니다. 새 값이 더 크면 실제 값만 넣습니다. 두 번 넣는 건 최솟값이 바뀌거나 같은 최솟값이 들어올 때뿐입니다.
꺼낼 때도 같은 기준을 사용합니다. 꺼낸 값이 현재 최솟값이면 한 번 더 꺼내 이전 최솟값으로 복원합니다. 같은 최솟값이 여러 번 들어오는 경우까지 처리하려고 push 조건에 등호를 포함했습니다.
코드
class MinStack {
Stack<Integer> stack = new Stack<>();
int minValue = Integer.MAX_VALUE;
public MinStack() {
}
public void push(int val) {
if(val <= minValue){
stack.push(minValue);
minValue = val;
}
stack.push(val);
}
public void pop() {
if(stack.pop() == minValue){
minValue=stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minValue;
}
}