LeetCode[day10] - Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Methods pop, top and getMin operations will always be called on non-empty stacks.

Input ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output [null,null,null,null,-3,null,0,-2]
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에서는 point를 올려주고, 값을 넣어준다.

 - pop에서는 point를 내려주고, 값을 빼준다.

 - top에서는 현재 point의 값을 보여준다.

 - getMin()에서는 누적된 값들을 for문으로 돌려서 min을 찾는다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 생각한 내용을 구현하는 것에 대한 큰 어려움은 없었다.

 - 옳은 방법인지는 모르겠지만, Stack의 사이즈를 8500으로 정해놨다.

 

3. 내가 작성한 알고리즘

 

public class MinStack {
    /** initialize your data structure here. */
    int point = -1;
    Integer[] contents = new Integer[8500];
    public MinStack() {
 
    }
 
    public void push(int x) {
        point++;
        contents[point] = x;
    }
 
    public void pop() {
        contents[point] = null;
        point--;
    }
 
    public int top() {
        return contents[point];
    }
 
    public int getMin() {
        int min = Integer.MAX_VALUE;
        for(Integer number:contents){
            if(number != null){
                min = Math.min(number, min);    
            }
        }
        return min;
    }
}

4. 내가 작성한 알고리즘 결과

뒤에서 9프로

 

5. 내가 작성한 알고리즘 코드 개선해보기

 

 - 개선할 수 있는 포인트

 + getMin() 메소드의 영역에서 for문을 돌리는데, 이 때 O(N)의 시간복잡도가 사용된다.

 + 공간 복잡도를 늘리는 대신, 시간복잡도를 줄이자 ㅋㅋ

 

 - 개선 사항

 + minNumbers라는 것을 통해서, 해당 point에 어떤 값이 MIN의 값을 갖고 있는 지, 기록한다.

 + getMin()에서는 해당 point일 때, MIN 값을 가져오도록 해서, 별도로 min 값을 구하지 않는다.

public class MinStack {
    /** initialize your data structure here. */
    int point = -1;
    Integer[] numbers = new Integer[8500];
    Integer[] minNumbers = new Integer[8500];
    public MinStack() {
        
    }
 
    public void push(int x) {
        point++;
        numbers[point] = x;
        if(point==0){
            minNumbers[0] = x;
        }else{
            minNumbers[point] = Math.min(minNumbers[point-1], x);
        }
    }
 
    public void pop() {
        numbers[point] = null;
        minNumbers[point] = null;
        point--;
    }
 
    public int top(){
        return numbers[point];
    }
 
    public int getMin() {
        return minNumbers[point];
    }
}

 

6. 개선한 알고리즘에 대한 결과

 

효과는 훌륭했다...!

 

7. 다른 사람이 작성한 알고리즘 보기

 

class Elem{
    public int value;
    public int min;
    public Elem next;
 
    public Elem(int value, int min){
        this.value = value;
        this.min = min;
    }
}
 
public class MinStack {
    public Elem top;
 
    /** initialize your data structure here. */
    public MinStack() {
 
    }
 
    public void push(int x) {
        if(top == null){
            top = new Elem(x, x);
        }else{
            Elem e = new Elem(x, Math.min(x,top.min));
            e.next = top;
            top = e;
        }
 
    }
 
    public void pop() {
        if(top == null)
            return;
        Elem temp = top.next;
        top.next = null;
        top = temp;
 
    }
 
    public int top() {
        if(top == null)
            return -1;
        return top.value;
    }
 
    public int getMin() {
        if(top == null)
            return -1;
        return top.min;
    }
}

 

8. 다른 사람이 작성한 알고리즘을 보고 배운점

 - MinStack을 Node를 통해서 연결한다. 참 좋다. 좋아. 대단하다~~.

 - push, pop일 때는 O(1), 노드에는 정보가 담겨져 있다.

 - 해당 노드에는 MIN의 정보가 담겨져있다.

 

9. 짝짝짝 결과

 

대단하다.

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3292/

Account Login - LeetCode