定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

Question

class MinStack(object):

#1构造函数
def __init__(self):
    self.stack1 = []
    self.stack2 = []


#1对栈进行push操作

def push(self, x):     
#首先如果将输入的元素直接放在栈1就行了。
    self.stack1.append(x)
#2对于栈2需要将待加入的数据进行比较，保证栈2顶端的数据是最小的。
    if not self.stack1:
        self.stack2.append(x)
#如果是最小的就直接放入，否则的话就舍弃。
    else:

        if self.stack2[-1] < x:
            self.stack2.append(self.stack2[-1])
        else :
            self.stack2.append(x)


#2对栈进行pop操作

def pop(self):
    self.stack1.pop()
    self.stack2.pop()
#直接对栈进行pop操作就可    
    # self.stack1.pop()
    # self.stack2.pop()

#获取栈顶元素
def top(self):
    if stack1 :
        return self.stack1[-1]
    else:
        return


def min(self):
    return self.stack2[-1]

class MinStack(object):

#1构造函数
def __init__(self):
    self.stack1 = []
    self.stack2 = []


#1对栈进行push操作

def push(self, x):     
#首先如果将输入的元素直接放在栈1就行了。
    self.stack1.append(x)
#2对于栈2需要将待加入的数据进行比较，保证栈2顶端的数据是最小的。
    if not self.stack1:
        self.stack2.append(x)
#如果是最小的就直接放入，否则的话就舍弃。
    else:

      **  if self.stack2[-1] < x:
            self.stack2.append(self.stack2[-1])**
        else :
            self.stack2.append(x)


#2对栈进行pop操作

def pop(self):
    self.stack1.pop()
    self.stack2.pop()
#直接对栈进行pop操作就可    
    # self.stack1.pop()
    # self.stack2.pop()

#获取栈顶元素
def top(self):
    if stack1 :
        return self.stack1[-1]
    else:
        return


def min(self):
    return self.stack2[-1]

用self.stack[-1]提示
IndexError: list index out of range
print(self.stack2[-1])
Line 20 in push (Solution.py)
Deserializer()._deserialize(json.dumps(p[0], separators=(",", ":")), "integer"))
Line 71 in helper_select_method (Solution.py)
ret.append(DriverSolution().helper_select_method(method, params[index], obj))
Line 121 in _driver (Solution.py)
_driver()
Line 130 in (Solution.py)
这种问题。

Answer 1

class MinStack(object):
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    
    #1对栈进行push操作
    def push(self, x):     
    #首先如果将输入的元素直接放在栈1就行了。
        self.stack1.append(x)
    #2对于栈2需要将待加入的数据进行比较，保证栈2顶端的数据是最小的。
        if not self.stack2:
            self.stack2.append(x)
    #如果是最小的就直接放入，否则的话就舍弃。
        else:
            if self.stack2[-1] > x:
                self.stack2[0] = x
        return self.stack1
    #2对栈进行pop操作
    def pop(self):
        if self.stack1:
            self.stack1.pop()
            self.stack2[0] = sorted(self.stack1, reverse=True)[-1]
        return self.stack1
    #直接对栈进行pop操作就可    
        # self.stack1.pop()
        # self.stack2.pop()
    #获取栈顶元素
    def top(self):
        if self.stack1 :
            return self.stack1[-1]
        else:
            return None
    
    def min(self):
        return self.stack2[-1]
    def __repr__(self):
        return  '[{}]'.format(','.join(map(str, self.stack1)))

a = MinStack()
a.push(4)
print(a)
a.push(8)
print(a, a.min())
a.pop()
print(a)
print(a.min())