Python编程题32--最小栈

题目

栈是一种常见的数据结构，其特点是 先进后出，也就是说最先放进去的元素，需要到最后才能取出来。

请使用 列表list 实现一个能在 常数时间 内检索到最小元素的栈，需实现以下操作：

• push(x) -- 将元素 x 压入栈顶
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• min() -- 检索并返回栈中的最小元素
• empty() -- 判断栈是否为空
• size() -- 获取栈的长度

说明：假设每次调用 pop / top / min 操作都能保证栈不为空。

实现思路1

• 使用一个栈 s 用于保存每个元素，另外再使用一个栈 min_s 用于保存当前的最小值
• 每次入栈时，把元素压入栈 s 的栈顶，同时把栈 s 中的最小值，压入栈 min_s 的栈顶
• 每次出栈时，两个栈都需要执行 pop() 操作
• 如果要获取栈顶元素，则直接取栈 s 的栈顶元素；如果要获取栈中的最小值，则直接取栈 min_s 的栈顶元素

代码实现1

class MinStack:

    def __init__(self):
        self.s = []
        self.min_s = []

    def push(self, x):
        self.s.append(x)
        if self.min_s == [] or self.min_s[-1] > x:
            self.min_s.append(x)
        else:
            self.min_s.append(self.min_s[-1])

    def pop(self):
        self.s.pop()
        self.min_s.pop()

    def top(self):
        return self.s[-1]

    def min(self):
        return self.min_s[-1]

    def empty(self):
        return self.s == []

    def size(self):
        return len(self.s)

实现思路2

• 只使用一个栈，同时保存当前值和栈内的最小值
• 每次入栈时，入栈元素为元组形式：（最小值，当前值），每次出栈时，把栈顶的元组执行出栈即可
• 因为栈顶的元组中同时保存了栈内的最小值和栈顶的当前值，所以栈顶元组中，第一个值即为栈内最小值，第二个值即为栈顶当前值

代码实现2

class MinStack:

    def __init__(self):
        self.s = []

    def push(self, x):
        if self.s == [] or self.s[-1][0] > x:
            self.s.append((x, x))
        else:
            self.s.append((self.s[-1][0], x))

    def pop(self):
        self.s.pop()

    def top(self):
        return self.s[-1][1]

    def min(self):
        return self.s[-1][0]

    def empty(self):
        return self.s == []

    def size(self):
        return len(self.s)

更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）