155. 最小栈 - 简单

155. 最小栈

解法

• 时间复杂度
  对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是
  O(1)，我们定义的每个操作最多调用栈操作两次。
• 空间复杂度
  其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。

class MinStack {
    /** initialize your data structure here. */
    var list: [Int] = []
    //记录当前最小值
    var minNum: Int?
    //只存最小值
    var minNums: [Int] = []

    init() {}

    func push(_ x: Int) {
        list.append(x)
        minNum = min(minNum ?? .max, x)
        if minNum == x {
            minNums.append(minNum!)
        }
    }

    func pop() {
        let p = list.removeLast()
        if minNum == p {
            minNum = list.min()
            minNums.removeLast()
        }
    }

    func top() -> Int {
        return list.last ?? 0
    }

    func getMin() -> Int {
        return minNums.last ?? 0
    }
}