https://leetcode.com/problems/min-stack/description/
코드설명
구현(Implementation) + 아이디어(Idea) 를 활용합니다.
문제의 조건에 시간복잡도 O(1) 안에 모든 연산문을 처리해야합니다. 처음에는 HashMap을 사용해야하나와 같은 생각을 했습니다.
풀이방식입니다.
배열을 유지하면서 현재 top값을 기준으로 가장 최소값을 계속해서 갱신해나갑니다.
문제의 Example 1을 보면,
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2위의 값들을 테이블로 표현해보겠습니다.
1. minStack.push(-2) :
[ -2 ][ -2 ]
2. minStack.push(0) :
[ 0 ][ - 2 ]
[ -2 ][ -2 ]
3. minStack.push(-3) :
[ 3 ][ -2 ]
[ 0 ][ - 2 ]
[ -2 ][ -2 ]
이런식으로 유지됩니다.
항상 하나의 위치에서의 최소값을 삽입/출력할 때 계산해낼 수 있으므로 O(1)의 시간복잡도를 만족합니다.
코드
class MinStack {
int[][] arr;
int top;
public MinStack() {
arr = new int[3 * 10000 + 1][2];
for(int[] v : arr){
Arrays.fill(v, Integer.MAX_VALUE);
}
top = 0;
}
public void push(int val) {
int minValue = getMin();
top += 1;
arr[top][0] = val;
if(minValue > val){
arr[top][1] = val;
}else {
arr[top][1] = minValue;
}
}
public void pop() {
top--;
}
public int top() {
return arr[top][0];
}
//O(1)에 어떻게 최소값을 알 수 있을까?
public int getMin() {
return arr[top][1];
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/