LeetCode-热题100：155. 最小栈

代码描述

设计一个支持 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.

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 `3 * 10⁴次

代码及注释

type MinStack struct {
    min   []int  // 存储最小值的辅助栈
    stack []int  // 主栈
}

// 构造函数，初始化栈
func Constructor() MinStack {
    return MinStack{stack: []int{}}
}

// 入栈操作
func (this *MinStack) Push(val int) {
    // 如果辅助栈为空或当前值小于等于辅助栈的栈顶元素，则将当前值压入辅助栈
    if len(this.min) == 0 || val <= this.GetMin() {
        this.min = append(this.min, val)
    }
    // 将值压入主栈
    this.stack = append(this.stack, val)
}

// 出栈操作
func (this *MinStack) Pop() {
    // 如果主栈的栈顶元素等于辅助栈的栈顶元素，则辅助栈也出栈
    if this.Top() == this.GetMin() {
        this.min = this.min[:len(this.min)-1]
    }
    // 主栈出栈
    this.stack = this.stack[:len(this.stack)-1]
}

// 获取栈顶元素
func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

// 获取最小值
func (this *MinStack) GetMin() int {
    return this.min[len(this.min)-1]
}

/**
 * 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();
 */

代码解释

• 使用两个栈，一个用于正常的栈操作，另一个用于存储最小值。
• 当 Push 操作时，如果当前值小于等于辅助栈的栈顶元素或辅助栈为空，则将当前值压入辅助栈。
• 当 Pop 操作时，如果主栈的栈顶元素等于辅助栈的栈顶元素，则辅助栈也出栈。

这样可以保证辅助栈的栈顶始终存储当前主栈中的最小值，从而在常数时间内获取栈的最小值。

该算法的时间复杂度为 O(1)。