题目
剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例：
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2. 复制代码
分析
首先根据题目要求，分析需要实现的功能点
- 实现一个栈的数据结构
实现的类需要具备先进先出的特点 - 包含push，pop，min，top数据操作
具备添加，删除，取最小值，取栈顶值等方法 - 时间复杂度为O(1)
通常要求时间复杂度低的实现都需要用到空间换时间的方法
思路
- 首先如何实现一个栈的数据结构
在javascript中，数组自带push 和 pop方法可以模拟一个栈的数据结构
那么考虑定义一个x_stack数组来存放数据 - 完成push，pop，min，top数据操作
这里开始就需要注意了，这些操作需要结合第三点来思考，数组中的push与pop本身满足O(1)复杂度，可以直接拿来用，但min操作需要知道栈中的所有值才能确定出来，为了达到O(1)的复杂度，我们就需要借助辅助数组来记录不同栈状态下的最小值是多少，我们可以记为min_stack - 接下来就是方法实现的一些细节了
- push 在添加新元素的时候，需要注意更新最小值，可以从最小值数组中取出当前最小值做对比，如果小于当前最小值，就把新元素添加到最小值数组中，反之，则把之前的最小值添加到最小值数组中
- pop 删除操作比较简单，同步使用 pop 方法删除
x_statck 和 min_stack的顶端元素即可 - top 直接获取数组的长度，取最后一个元素即是栈的顶部元素
- min 直接获取最小值数组的长度，取最后一个元素即是当前栈中的最小值
实现
class MinStack { x_stack: number[] min_stack: number[] constructor() { this.x_stack = [] this.min_stack = [] } push(x: number): void { this.x_stack.push(x) if (this.x_stack.length === 1) { this.min_stack.push(x) } else { const min = this.min_stack[this.min_stack.length - 1] if (min > x) { this.min_stack.push(x) } else { this.min_stack.push(min) } } } pop(): void { this.x_stack.pop() this.min_stack.pop() } top(): number { return this.x_stack[this.x_stack.length - 1] } min(): number { return this.min_stack[this.min_stack.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() */
