题目
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
解答
存一个最小值
作者：lovesora
链接：
/**
* initialize your data structure here.
*/
var MinStack = function () {
this.stack = []
this.min = null
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
this.stack.push(x)
if (this.min > x || this.min === null) {
this.min = x
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
const pop = this.stack.pop()
if (pop === this.min) {
this.min = Math.min(...this.stack)
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.stack[this.stack.length - 1]
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
return this.min
};
Runtime: 96 ms, faster than 93.84% of JavaScript online submissions for Min Stack.
Memory Usage: 44.5 MB, less than 45.71% of JavaScript online submissions for Min Stack.
第15行被坑了一下，因为一般遇到需要判断null都会习惯性写成：!this.min。
if (this.min > x || !this.min) {
this.min = x
}
但是0就是false，也就是说只要min是0，不管再输入什么值，都会改写掉最小值。如果最小值是0，就永远无法存到。
因此只能写成this.min === null。可以说这是偷懒的下场。。
this.min = this.stack.length ? this.stack.reduce((min, cur) => Math.min(min, cur), Number.MAX_SAFE_INTEGER) : null
感觉明显复杂了很多。
还有用for循环遍历就更不用提了。
不过那个解答return pop了，而其实不用，因为pop函数return的是{void}，也就是说无需return
34行对top的处理，这是我看到最好的。。
之前的想法，是先pop出顶上的值，再push回去，明显绕了一大圈。
为了避免判断0的情况，想到了先用最大值赋值min的做法：
var MinStack = function () {
this.stack = []
this.min = Number.MAX_SAFE_INTEGER // 赋值
};
MinStack.prototype.push = function (x) {
this.stack.push(x)
this.min = x < this.min ? x : this.min // 没有null的情况可以直接判断
};
// 剩下的都一样
...
Runtime: 108 ms, faster than 62.53% of JavaScript online submissions for Min Stack.
Memory Usage: 44.7 MB, less than 27.62% of JavaScript online submissions for Min Stack.
感觉比之前要慢了不少。看来每次判断null比用最大值，更划算一些。
go
go似乎没发用存一个最小值实现。
首先min没法定义为null，因为是int类型的，默认零值就是0了。但如果定义为0，那么万一来的数全比0大呢？如果专门对零做判断，万一来的最小值是0呢？
min也没法定义为最大安全数，因为最大安全数分int32和int64，但就是没有int的最大数。
其次go没有类似于js的math.Min，只能比较float64，而且只能是两两比较。
只能想到一个比较原始的做法来取最小值：
...
for _, elem := range this.stack {
if elem < this.min {
this.min = elem
}
runtime.Gosched()
}
...
看到题解，普遍采用的是多存一个辅助栈的做法：
即，新开一个数组min，如果新push进来的数小于等于min的最小数，就push进min；出栈的时候，如果辅助栈顶和原来额数组一样，那么也要出栈一个，不然就不出栈。
type MinStack struct {
data []int
min []int
}
/** initialize your data structure here. */
func Constructor() MinStack {
var stack MinStack
return stack
}
func (this *MinStack) Push(x int) {
this.data = append(this.data, x)
if len(this.min) == 0 || this.min[len(this.min)-1] >= x { // 判断为0感觉是为了防止初值时的panic
this.min = append(this.min, x)
}
}
func (this *MinStack) Pop() {
if this.min[len(this.min)-1] == this.data[len(this.data)-1] {
this.min = this.min[0 : len(this.min)-1]
}
this.data = this.data[0 : len(this.data)-1]
}
func (this *MinStack) Top() int {
if len(this.data) == 0 { // 防止一上来先Top()，导致panic
return 0
}
return this.data[len(this.data)-1]
}
func (this *MinStack) GetMin() int {
if len(this.min) == 0 { // 防止一上来先getmin()，导致panic
return 0
}
return this.min[len(this.min)-1]
}
Runtime: 12 ms, faster than 100.00% of Go online submissions for Min Stack.
Memory Usage: 8.2 MB, less than 54.55% of Go online submissions forMin Stack.
看到了一个用链表的做法
感觉会更优一点，毕竟需要读取的只是最小值。
// ======= chain ========
type Node struct {
data int
next *Node
}
type Stack struct {
head *Node
}
func NewStack() *Stack {
return &Stack{
head: &Node{},
}
}
func (s *Stack) push(v int) {
n := &Node{
data: v,
next: nil,
}
n.next = s.head.next
s.head.next = n
}
func (s *Stack) pop() {
s.head.next = s.head.next.next
}
func (s *Stack) isEmpty() bool {
return s.head.next == nil
}
func (s *Stack) top() int {
if s.head.next != nil {
return s.head.next.data
}
return 0
}
type MinStack struct {
data []int
min *Stack
}
// ==== 上面都是链表的定义，下面开始答题 ====
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{
data: []int{},
min: NewStack(),
}
}
func (this *MinStack) Push(x int) {
this.data = append(this.data, x)
if this.min.isEmpty() || this.min.top() >= x {
this.min.push(x)
}
}
func (this *MinStack) Pop() {
if this.min.top() == this.data[len(this.data)-1] {
this.min.pop()
}
this.data = this.data[0 : len(this.data)-1]
}
func (this *MinStack) Top() int {
if len(this.data) == 0 {
return 0
}
return this.data[len(this.data)-1]
}
func (this *MinStack) GetMin() int {
return this.min.top()
}
Runtime: 20 ms, faster than 75.68% of Go online submissions for Min Stack.
Memory Usage: 8.5 MB, less than 14.29% of Go online submissions forMin Stack.
好像反而慢了很多。。。可能是因为链表的操作更加麻烦吧