最小栈

算法思路

LeetCode 155：实现栈的 push、pop、top，并在 O(1) 内返回当前最小值。

用辅助栈同步记录「到当前位置为止的最小值」：

• push(x)：主栈入栈；若辅助栈为空或 x <= 辅助栈顶，辅助栈也入栈 x
• pop()：主栈弹出；若弹出值等于辅助栈顶，辅助栈也弹出
• top()：主栈栈顶
• getMin()：辅助栈栈顶

每个元素最多入辅助栈一次，空间 O(n)。

python

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.min_stack: list[int] = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

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

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

js

class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    push(val) {
        this.stack.push(val);
        const n = this.minStack.length;
        if (n === 0 || val <= this.minStack[n - 1]) {
            this.minStack.push(val);
        }
    }

    pop() {
        const val = this.stack.pop();
        const n = this.minStack.length;
        if (n > 0 && val === this.minStack[n - 1]) {
            this.minStack.pop();
        }
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

go

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

func Constructor() MinStack {
    return MinStack{}
}

func (s *MinStack) Push(val int) {
    s.stack = append(s.stack, val)
    n := len(s.minStack)
    if n == 0 || val <= s.minStack[n-1] {
        s.minStack = append(s.minStack, val)
    }
}

func (s *MinStack) Pop() {
    val := s.stack[len(s.stack)-1]
    s.stack = s.stack[:len(s.stack)-1]
    n := len(s.minStack)
    if n > 0 && val == s.minStack[n-1] {
        s.minStack = s.minStack[:n-1]
    }
}

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

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