155. 最小栈(Easy)

题目描述

设计栈，支持 push、pop、top 等操作，使得常数时间内检索到最小值。

• push
• pop
• top
• getMin

样例

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

题目解析

存在两种思路：

第一种，每次添加进入的时候，存入当前元素的最小值。

LeetCode 官方图解

第二种，维持一个递减的最小栈。

代码

第一种，每次添加进入的时候，存入当前元素的最小值。

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

/** initialize your data structure here. */
func Constructor() MinStack {
    return  MinStack{stack: []int{}, 
                     minStack: []int{math.MaxInt64},
            }
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func (this *MinStack) Push(x int)  {
    this.stack = append(this.stack, x)
    this.minStack = append(this.minStack,
                           min(x, this.minStack[len(this.minStack) - 1])) // 每次存入最小值
}


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]
}

第二种，维持一个递减的最小栈。

class MinStack:

    def __init__(self):
        self.stack_data = []
        self.min_data = [] # 单调栈，里面的元素始终是递减的

    def push(self, x: int) -> None:
        self.stack_data.append(x)
        if not self.min_data or x <= self.min_data[-1]:
            self.min_data.append(x)

    def pop(self) -> None:
        x = self.stack_data.pop()
        if self.min_data and x == self.min_data[-1]:
            self.min_data.pop()

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

    def getMin(self) -> int:
        if self.min_data: # 当存在最小值的时候，返回单调栈的最小值
            return self.min_data[-1]
        else: # 当不存在最小值的，返回元素的值。
            return self.stack_data[-1]