21、包含min函数的栈

因此,想到构造一个辅助栈S_helper,每次往栈S中添加到一个元素时,辅助栈S_helper都会在栈顶添加一次当前S里最小的元素值。这样每次调用min时,只需要返回辅助栈的栈顶元素即可。 当然在删除S中的栈顶元素时,也会删除S_helper中的栈顶元素。

注意,要明确每次在辅助站中添加的元素是谁。
若新添加的元素小于辅助栈 的栈顶元素(也就是小于当前S中的最小元素),那么就在栈顶添加新的value。
如果新添加的value大于辅助栈的栈顶元素,那么就继续在辅助栈中添加辅助栈的栈顶元素即可。

代码实现:

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.S = []
        self.S_helper = []
    def push(self, node):
        self.S.append(node)
        #如果辅助站为空,或新来的node值大于辅助站的栈顶元素,
        # 那么就更新辅助站的栈顶元素为最小值
        if len(self.S_helper) == 0 or node < self.S_helper[-1]:
            self.S_helper.append(node)
        else:
            self.S_helper.append(self.S_helper[-1])
    def pop(self):
        res = self.S.pop()
        res_helper = self.S_helper.pop()
        return res
    def top(self):
        return self.S[-1]
    def min(self):
        return self.S_helper[-1]
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容