leetcode with python:155. Min Stack

题目:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

设计一个stack,它有push(加入值),pop(去除最后一个值),top(回传最后一个值),getMin(回传最小值)的功能

很新奇的题目,要我们设计一系列函数
不过这题有个严苛的限制,所有函数的时间複杂度都只能是O(1)

class MinStack:    def __init__(self):        self.stack=[]        self.minstack=[]    def push(self, val: int) -> None:        if self.minstack==[]:            self.minstack.append(val)        else:            if self.minstack[-1]>val:                self.minstack.append(val)            else:                self.minstack.append(self.minstack[-1])        self.stack.append(val)    def pop(self) -> None:        self.stack.pop()        self.minstack.pop()     def top(self) -> int:        return self.stack[-1]    def getMin(self) -> int:        return self.minstack[-1]

我们逐各个函数来解释:
(1)init:
宣告一个纪录值的stack跟一个纪录stack历史最小值的minstack
(2)push:
stack直接append值
minstack则是val和minstack[-1] (val进来前的最小值)比大小,小的append入minstack(新最小值)
若minstack为空直接append值
(3)pop:
stack跟minstack都将最后一个值pop掉
(4)top:
回传stack[-1]即可
(5)getMin:
回传minstack[-1]即可
最后执行时间57ms(faster than 98.00%)

那我们下题见