[LeetCode] 155. Min Stack / Swift

[문제 보기]

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(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.

 

Example 1:

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

 

Constraints:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

 

https://leetcode.com/problems/min-stack/

Min Stack - LeetCode

 

---

상수시간내에 작동하는 push, pop, top, getMin 메서드를 가진 stack을 구현하세요.

 

풀이 과정

기본 스택과 최소값이 기본 스택에 어디에 있는지 인덱스를 가지는 또 다른 스택 이렇게 2개의 스택을 이용해서 풀었다.

 

step1

step1: 우선 우리가 알고있는 기본 스택인 s1와 최소값들을 가리킬 또 다른 스택 s2를 만들어준다.

 

step2

s1의 갯수가 1일때는 처음 시작하는 경우라서 비교할 값이 없으므로 0으로 채워준다.

step3

새로운 원소(5)가 들어왔을 때이다.  s1에는 그대로 넣어주면 되고 s2은 이전까지 있었던 최소값 = (s2의 맨위가 가리키는 원소값)과 현재 들어온 값(5)을 비교한다. 만약 현재 들어온 값(5)이 작다면 s2에는 현재 들어온 값의 위치(s1.count - 1)를 넣어주면 되고, 현재 들어온 값(5)이 더 크다면 이전에 있었던 최소값의 위치를 그대로 넣어준다

step4

s2에는 항상 이전까지의 최소값의 위치를 저장되게한다. 이 작업은 pop()작업때 원소가 삭제되어도 삽입되기 전까지의 최소를 유지하므로 현재단계에서의 항상 최소를 가리키게 된다.

 

---

소스코드(Swift)

class MinStack {

    var stack: [Int]
    var minStack: [Int]
    /** initialize your data structure here. */
    init() {
        stack = [Int]()
        minStack = [Int]()
    }
    
    func push(_ val: Int) {
        stack.append(val)    
        if stack.count == 1 {
            minStack.append(0)
            return
        }
        
        let beforeMinIndex = minStack[stack.count - 2]
        if val > stack[beforeMinIndex] {
            minStack.append(minStack[beforeMinIndex])
        } else {
            minStack.append(stack.count - 1)
        }
    }
    
    func pop() {
        stack.removeLast()
        minStack.removeLast()
    }
    
    func top() -> Int {
        return stack.last!
    }
    
    func getMin() -> Int {
        return stack[minStack.last!]
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * let obj = MinStack()
 * obj.push(val)
 * obj.pop()
 * let ret_3: Int = obj.top()
 * let ret_4: Int = obj.getMin()
 */