LeetCode如何實現(xiàn)包含min函數(shù)的棧

題目描述

定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時間復(fù)雜度都是 O(1)。

各函數(shù)的調(diào)用總次數(shù)不超過 20000 次

題目樣例

示例

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

題目思考

1. 內(nèi)部需要什么數(shù)據(jù)結(jié)構(gòu)來滿足所有操作都是 O(1), 一個棧夠嗎?

解決方案

思路

• 要使得 push 和 pop 的復(fù)雜度為 O(1), 傳統(tǒng)的棧就可以搞定, 難點在于如何使得 min 函數(shù)也為 O(1)
• 如果我們能一直維護當前所有元素的最小值, 那么 min 函數(shù)直接返回它就可以, 但問題是在 pop 的時候有可能會正好 pop 這個最小值, pop 之后的最小值(也即原來的次小值)如何得到呢?
• 要存儲多個最小值, 顯然一個變量不夠用. 而根據(jù)上一步的分析, 這里我們可以考慮額外引入一個              單調(diào)遞減棧, 棧頂存當前最小值, 下面依次是次小, 第三小...
• 這樣如果 pop 了最小值的話, 這個單調(diào)棧的棧頂仍會保存 pop 后的最小值, 每次 min 只需要取這個棧的棧頂即可
• 而 push 的時候也需要額外的操作, 由于是單調(diào)棧, 只需要在新的值              小于等于棧頂?shù)臅r候才 push 到單調(diào)棧中.特別注意在等于棧頂?shù)臅r候也要 push 到單調(diào)棧中, 這是因為如果對于重復(fù)的最小值 x 不 push, 那么在后續(xù)的 pop 其中一個 x 之后, 棧頂(不再是 x)就和實際最小值(仍為 x)不一致了

復(fù)雜度

• 時間復(fù)雜度              O(1)
• 各種操作都是常數(shù)復(fù)雜度
• 空間復(fù)雜度              O(N)
• 使用了兩個棧

代碼

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        # 一個普通棧和一個單調(diào)遞減棧
        self.minstack = []
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.minstack or x <= self.minstack[-1]:
            # 如果單調(diào)棧頂為空或者當前新值小于等于單調(diào)棧頂才push
            # 注意這里等于也需要push. 如果對于重復(fù)的最小值 x 不 push, 那么在后續(xù)的 pop 其中一個 x 之后, 棧頂(不再是 x)就和實際最小值(仍為 x)不一致了
            self.minstack.append(x)

    def pop(self) -> None:
        if not self.stack:
            return
        x = self.stack.pop()
        if x == self.minstack[-1]:
            # 如果單調(diào)棧頂恰好等于pop的值, 也要pop單調(diào)棧
            self.minstack.pop()

    def top(self) -> int:
        if not self.stack:
            return -1
        return self.stack[-1]

    def min(self) -> int:
        if not self.minstack:
            return -1
        return self.minstack[-1]