剑指Offer第20题-包含min函数的栈

题目

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

思路

主要有两种思路

  1. (时间换空间)只维护一个栈,需要取最小值的时候对栈中的元素进行遍历,找出最小值。当栈非常大的时候,这种思路的代价就很大。
  2. (空间换时间)多维护一个最小值栈min_stack。每次push的时候,检查最小值栈是否为空,若为空直接插入,不为空则判断插入值是否小于栈顶元素,若小于则插入。pop时我们如果最小值栈栈顶的元素和pop的元素相等,则将最小值栈顶元素也pop出去。

有人可能会问,为什么需要维护最小值栈呢,直接维护最小值不就好了吗?问题在于我们是有可能pop的,万一stack中被pop出去的值刚好是你记录的最小值,此时你就不知道接下来的最小值该取什么了。

代码

思路二

class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, node):
        # write code here
        self.stack.append(node)

        if not self.min_stack or self.min_stack[-1] > node: 
            self.min_stack.append(node)
    def pop(self):
        # write code here
        pop = self.stack.pop()
        if self.min_stack[-1] == pop: 
            self.min_stack.pop()
        return pop

    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.min_stack[-1]
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。