剣指offer第20題_min関数を含むスタック_Python

タイトルの説明

スタックのデータ構造を定義する

は、スタックに含まれる最小要素を得ることができるmin関数をこのタイプで実現する.時間複雑度はO(1)

であるべきである
理解する

スタック

とは

アルゴリズム複雑度

問題を解く構想.
考え方1

class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, node):
        self.stack.append(node)
        if self.min_stack == [] or node <= self.min():
            self.min_stack.append(node)
    def pop(self):
        if self.stack != []:
            if self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            return self.stack.pop()
    def top(self):
        return self.stack[-1]
    def min(self):
        if self.min_stack[-1] != None:
            return self.min_stack[-1]

拡張リファレンス

class MinInStack:
    def __init__(self):
        self.stack = []
        #      
        self.min_stack = []
        #     
        self.length = 0

    def isEmpty(self):
        #       
        return self.length == 0

    def getLength(self):
        #       
        return self.length

    def min(self):
        #      
        if self.isEmpty():
            print("Stack is empty!")
            return
        if self.min_stack:
            return self.min_stack[-1]

    def push(self, data):
        if not isinstance(data, int) and not isinstance(data, float):
            print("The element must be numeric!")
            return
        #   
        self.stack.append(data)
        self.length += 1
        #             
        if self.min_stack == [] or data < self.min():
            self.min_stack.append(data)
        else:
            self.min_stack.append(self.min())

    def pop(self):
        #   
        if self.isEmpty():
            print("Stack is empty!")
            return
        data = self.stack.pop()
        self.min_stack.pop()
        self.length -= 1
        return data

    def clear(self):
        #    
        self.stack = []
        self.min_stack = []
        self.length = 0