2023-9-2

9-2

栈与队列

题号剑指 Offer 30. 包含 min 函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

思路：pop和push的时间复杂度本身就是O(1)所以问题就是怎么实现min的复杂度也为O(1)，这里可以使用辅助栈来实现，辅助栈非严格降序保存a栈中的数据

class MinStack {
    private nums = []
    private nums2 = []
    constructor() {

    }

    push(x: number): void {
        this.nums.push(x)
        if(this.nums2.length===0||this.nums2[this.nums2.length-1]>=x)this.nums2.push(x)
    }

    pop(): void {
        let y = this.nums.pop()
        if(y===this.nums2[this.nums2.length-1])this.nums2.pop()
    }

    top(): number {
        return this.nums[this.nums.length-1]
    }

    min(): number {
        return this.nums2[this.nums2.length-1]
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */