[Stack] Min Stack

최소 스택

Min Stack - LeetCode

푸시, 팝, 상단 및 일정한 시간에 최소 요소 검색을 지원하는 스택을 설계합니다.

클래스를 구현합니다 MinStack.

• MinStack()스택 개체를 초기화합니다.
• void push(int val)요소를 val스택에 푸시합니다.
• void pop()스택 맨 위에 있는 요소를 제거합니다.
• int top()스택의 최상위 요소를 가져옵니다.
• int getMin()스택에서 최소 요소를 검색합니다.

O(1)각 기능에 대해 시간 복잡도가 있는 솔루션을 구현해야 합니다 .

 

예시 1:

입력 
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[- 
3 ],[],[],[],[]] 출력 
[null,null,null,null,-3,null,0,-2] 설명 
MinStack minStack = new MinStack(); 
minStack.push(-2); 
minStack.push(0); 
minStack.push(-3); 
minStack.getMin(); // -3을 반환합니다. 
minStack.pop(); 
minStack.top(); // 0을 반환합니다. 
minStack.getMin(); // -2를 반환

 

제약:

• -2^31 <= val <= 2^31 - 1
• 메서드 pop및 작업 top은 항상 비어 있지 않은getMin 스택 에서 호출됩니다 .
• 대부분의 호출은 , , 및 으로 이루어집니다 .3 * 10^4 push/pop/top/getMin

---

1.첫번째 시도

class MinStack {

    int top = -1;
    ArrayList<Integer> stack = new ArrayList<>(); 
    ArrayList<Integer> minStack = new ArrayList<>();

    public MinStack() {
        
    }
    
    public void push(int val) {
        stack.add(val);
        if(top==-1){
            minStack.add(val);
        }else{
            minStack.add( Math.min(minStack.get(top),val));
        }
       
        top++;
    }
    
    public void pop() {
        stack.remove(top);
        minStack.remove(top);

        top--;
    }
    
    public int top() {
        return stack.get(top);
    }
    
    public int getMin() {
        return minStack.get(top);
    }
}

/**
 * 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();
 */

자료구조 스택을 구현하는 문제였습니다.

스택의 특성은 LIFO(last in fisrt out) 늦게 들어온 스택이 가장먼저 나간다는 특징을 가지고 있습니다.

top 이라는 포인터를 사용하여 초기 값은 -1로 시작하여

push() 할 때마다 top++ 하여 포인터를 한칸씩 이동시킨다.

pop() 할 때마다 top--하여 포인터를 한칸씩 뒤로 이동 시킨다.

top()은 스택에 가장 위에 값을 확인 하기 위해 현재 포인터 top에 값을 반환한다.

이렇게 쉽게 스택 자료구조를 구현 할 수 있지만 getMin() 현재 스택의 값중 가장 작은 값을 반환하라는

요구사항이 있습니다. 

최소값을 구하기 위해 minStack을 사용하여 push할때마다 Math.min() 사용하여 최소값을 가지는 스택을 따로 구현하였습니다

push()할 때 stack과 minStack에 배열에 각자 역할이 다른 데이터들이 저장하게되고

pop()또한 같이 데이터가 삭제되어 현재 stack의 최소값을 확인 할 수 있었다. 

이렇게 문제를 해결 하였을때의 시간복잡도 O(1), 공간복잡도 O(n)+O(n)+O(n) = O(3n) = O(n)로 나왔습니다.