招行算法2020屆實習技術面程式設計題：實作O(1)最小棧（手撸代碼）

何為最小棧？棧最基礎的操作是壓棧(push)和退棧(pop)，現在需要增加一個傳回棧内最小值的函數(get_min)，要求get_min函數的時間複雜度為o(1)。python的棧肯定是使用list實作，隻要将list的append和pop封裝到stack類中，即實作了壓棧和退棧。如果不考慮時間複雜度，我們第一反應一定是min()，min()可以在不開辟新空間的情況下o(n)的傳回棧内最小值。但是如果棧内元素很多，并且get_min方法需要頻繁調用時，min高耗時的缺點就被放大，那麼理想的方法就是空間換時間來降低時間複雜度。

#!/usr/bin/python
# -*- coding: utf-8 -*-

class stack(object):
    stack_list = []
    min_list = []
    min = None

    def push(self, x):
        if not self.stack_list:
            self.min = x
            self.min_list.append(self.min)
            self.stack_list.append(x)
            return
        self.stack_list.append(x)
        if self.min >= x:
            self.min = x
            self.min_list.append(self.min)
        return

    def pop(self):
        pop_result = None
        if self.stack_list:
            pop_result = self.stack_list[-1]
            if self.stack_list.pop() == self.min:
                self.min_list.pop()
                if self.min_list:
                    self.min = self.min_list[-1]
                else:
                    self.min = None
            return pop_result
        else:
            self.min = None
            return pop_result

    def print_stack(self):
        print "stack---->", self.stack_list
        return

    def get_min(self):
        return self.min
           

參考：

https://www.cnblogs.com/baiyb/p/8443337.html

https://blog.csdn.net/qq_36528804/article/details/82929234