題目:

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%)

那我們下題見