题目

155. 最小栈

思路

每次入栈的时候存储当前最小值即可

代码

class MinStack {
    var stack : ArrayList<Array<Int64>>
    // var minStack : ArrayList<Int64>
    init() {
        this.stack = ArrayList<Array<Int64>>()
    }
    
    func push(val: Int64): Unit {
        if(stack.size != 0){
            let oldMin = stack[stack.size-1][1]
            let newMin = min(oldMin, val)
            stack.append([val, newMin])
        }
        else{
            stack.append([val, val])
        }
    }
    
    func pop(): Unit {
        stack.remove(stack.size-1)
    }
    
    func top(): Int64 {
        return stack[stack.size-1][0]
    }
    
    func getMin(): Int64 {
        return stack[stack.size-1][1]
    }
}

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

复杂度

时间复杂度：
push: O(1)
pop: O(1)
top: O(1)
getMin: O(1)
空间复杂度：O(n)

这个 MinStack 实现非常有效，能够在常数时间内完成所需的操作，非常适合用于需要频繁获取最小值的场景。

遇到的坑

\

结果

cangjie