剣指offer(20)

913 ワード

剣指オフ

スタックのデータ構造を定義して、スタックに含まれる最小要素のmin関数(時間複雑度はO(1)とする.

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minstack = []
        #              O(1)，         
        #       
    def push(self, node):
        # write code here
        self.stack.append(node)# node    
        if not self.minstack or node < self.minstack[-1]:
            #          ，         node ，   node    
            self.minstack.append(node)
        else:
            #           ，           
            self.minstack.append(self.minstack[-1])
    def pop(self):
        # write code here
        if self.stack:
            # push  ，stack  ，minstack   
            self.stack.pop()
            self.minstack.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.minstack[-1]

チェーンは多項式の相乗を実現します.