LeetCode刷题1栈的最小值

LeetCode刷题1栈的最小值

Scroll Down

题目

  • 题目描述

    请设计一个栈,除了常规栈支持的 pop 与 push 函数以外,还支持 min 函数,该函数返回栈元素中的最小值。执行 push、pop 和 min 操作的时间复杂度必须为 O(1)。

  • 示例

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

解题思路

可以定义两个栈,一个栈用于存放普通数据(数据栈),另一个栈用于记录当前栈中的最小值(最小值栈)。

栈中最小值只有在入栈或出栈后才会发生变化。当入栈时,只需比较入栈元素是否小于原来栈中最小值,若小于将该元素值保存到最小值栈中;若大于等于,则将原来栈中最小值再次保存到最小值栈中。当出栈时,依次将数据栈和最小值栈中元素出栈即可。

获取栈中最小值只需要返回最小值栈的栈顶元素即可。

具体代码

class MinStack:
    def __init__(self):
        """初始化"""
        self.items = []  # 数据栈
        self.min_items = []  # 最小值栈

    def push(self, x: int) -> None:
        """入栈"""
        self.items.append(x)  # 将元素压入数据栈
        if (self.min_items and x < self.min_items[-1]) or not self.min_items:  # 如果最小值栈中有元素,且入栈元素小于栈顶元素或最小值栈是空栈
            self.min_items.append(x)  # 将元素压入最小值栈
        else:  # 最小值未发生变化
            self.min_items.append(self.min_items[-1])

    def pop(self) -> None:
        """出栈"""
        self.items.pop()
        self.min_items.pop()

    def top(self) -> int:
        """"获取栈顶元素"""
        return self.items[-1]

    def get_min(self) -> int:
        """获取栈中最小值"""
        return self.min_items[-1]