leetcode: 155. Min Stack

문제링크

풀이1

• 스택에는 저장할 값과 현재까지의 최솟값을 함께 저장한다.
• push할 값과 minValue 중 더 작은 값을 스택에 push한다.
• pop을 하면 minValue 값을 갱신한다.

class MinStack() {
    val stack = mutableListOf<Pair<Int, Int>>()
    var minValue = Int.MAX_VALUE
    
    fun push(`val`: Int) {
        if (minValue > `val`) {
            minValue = `val`
        }
        stack.add(Pair(`val`, minValue))
    }

    fun pop() {
        stack.removeAt(stack.size - 1)
        if (stack.isEmpty()) {
            minValue = Int.MAX_VALUE
        } else {
            minValue = stack[stack.size - 1].second
        }
    }

    fun top(): Int {
        return stack[stack.size - 1].first
    }

    fun getMin(): Int {
        return stack[stack.size - 1].second
    }

}

push, pop, top, getMin의 시간복잡도 : O(1)
공간복잡도 : O(N)

풀이2

• 풀이1의 방법과 거의 유사하다.
• push할 때 이전 값과 비교하여 더 작은 값을 push한다.

import kotlin.math.min

class MinStack() {
    val stack = mutableListOf<Pair<Int, Int>>()
    
    fun push(`val`: Int) {
        if (stack.isEmpty()) {
            stack.add(Pair(`val`, `val`))
        } else {
            val prev = this.getMin()
            stack.add(Pair(`val`, min(prev, `val`)))   
        }
    }

    fun pop() {
        stack.removeAt(stack.size - 1)
    }

    fun top(): Int {
        return stack[stack.size - 1].first
    }

    fun getMin(): Int {
        return stack[stack.size - 1].second
    }

}

push, pop, top, getMin의 시간복잡도 : O(1)
공간복잡도 : O(N)