最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。  

示例 1:

输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

---

辅助栈-python实现

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [math.inf]

    def push(self, val: int) -> None:
        self.stack.append(val)
        self.min_stack.append(min(val, self.getMin()))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]



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

辅助栈-go实现

type MinStack struct {
    stack []int
    minStack []int
    length int
}


func Constructor() MinStack {
    return MinStack{
        stack: []int{},
        minStack: []int{math.MaxInt64},
    }
}


func (this *MinStack) Push(val int)  {
    this.stack = append(this.stack, val)
    top := this.minStack[len(this.minStack)-1]
    this.minStack = append(this.minStack, min(top, val))
}


func (this *MinStack) Pop()  {
    this.stack = this.stack[:len(this.stack)-1]
    this.minStack = this.minStack[:len(this.minStack)-1]
}


func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}


func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

存储和最小值的差值

python实现

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_value = -1

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min_value = val
            return
        diff = val - self.min_value
        # 当出现更小的数时，此时更新min_value
        if diff < 0:
            self.min_value = val
        self.stack.append(diff)

    def pop(self) -> None:
        if not self.stack:
            return None
        diff = self.stack.pop()
        top = self.min_value + diff
        # 弹出时为负数，此时最小值即为栈顶值
        if diff < 0:
            top = self.min_value
            self.min_value = self.min_value - diff
        return top

    def top(self) -> int:
        if not self.stack:
            return -1
        diff = self.stack[-1]
        top = self.min_value + diff
        if diff < 0:
            top = self.min_value
        return top

    def getMin(self) -> int:
        if not self.stack:
            return -1
        return self.min_value



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

go实现

type MinStack struct {
    stack []int
    minValue int
}


func Constructor() MinStack {
    return MinStack{
        stack: []int{},
        minValue: 0,
    }
}


func (this *MinStack) Push(val int)  {
    if len(this.stack) == 0{
        this.stack = append(this.stack, 0)
        this.minValue = val
    }else{
        diff := val - this.minValue
        this.stack = append(this.stack, diff)
        if diff < 0{
            this.minValue = val
        }
    }
}


func (this *MinStack) Pop()  {
    if len(this.stack) > 0{
        diff := this.stack[len(this.stack)-1]
        if diff < 0{
            this.minValue = this.minValue - diff
        }
        this.stack = this.stack[:len(this.stack)-1]
    }
}


func (this *MinStack) Top() int {
    if len(this.stack) > 0{
        diff := this.stack[len(this.stack)-1]
        if diff < 0{
            top := this.minValue
            return top
        }else{
            top := diff + this.minValue
            return top
        }
    }
    return -1
}



func (this *MinStack) GetMin() int {
    return this.minValue
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */