Tag

【設(shè)計類】【?！?/p>

題目來源

155. 最小棧

題目解讀

本題是一個設(shè)計類的題目，設(shè)計一個最小棧類 MinStack() 實現(xiàn)：

• MinStack()：初始化堆棧對象；
• void push(int val)：將元素val推入堆棧；
• void pop()：刪除堆棧頂部的元素；
• int top()：獲取堆棧頂部的元素；
• int getMin()：獲取堆棧中的最小元素。

解題思路

方法一：輔助棧

維護兩個棧，一個棧就是常規(guī)的棧 stk1，另一個棧 stk2 用來存放已經(jīng)插入棧 stk1 中數(shù)字的最小值。

注意入棧和出棧操作時兩個棧都要更新。

實現(xiàn)代碼

class MinStack {
	
public:
	MinStack() {
		min_stk.push(INT_MAX);
	}

	void push(int val) {
		stk.push(val);
		min_stk.push(std::min(min_stk.top(), val));
	}

	void pop() {
		stk.pop();
		min_stk.pop();
	}

	int top() {
		return stk.top();
	}

	int getMin() {
		return min_stk.top();
	}

private:
	std::stack<int> stk;
	std::stack<int> min_stk;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

復(fù)雜度分析

時間復(fù)雜度：$O(1)$。

空間復(fù)雜度：$O(n)$，$n$ 為 操作次數(shù)。

方法二：一個棧

可以只使用一個棧來同時保存當(dāng)前的最小值和 val。

實現(xiàn)代碼

class MinStack {
private:
    stack<pair<int, int>> stk;
public:
    MinStack() {
        stk.push(make_pair(INT_MAX, INT_MAX));
    }
    
    void push(int val) {
        stk.push({min(stk.top().first, val), val});
    }
    
    void pop() {
        stk.pop();
    }
    
    int top() {
        return stk.top().second;
    }
    
    int getMin() {
        return stk.top().first;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

復(fù)雜度分析

時間復(fù)雜度：$O(1)$。

空間復(fù)雜度：$O(1)$。

方法三：棧中存放差值

現(xiàn)在我們維護一個變量 minVal，表示當(dāng)前插入的變量的最小值，棧中每次入棧的是 val 與 minVal 的差值 differ。現(xiàn)在進行具體分析：

• push(int val)：如果此時棧為空，我們更新 minVal = val，向棧中插入 0；如果此時棧非空，首先向棧中插入 diff，根據(jù) diff 的值來更新 minVal：
  • 如果 diff > 0，說明插入的 val 大于當(dāng)前的 minVal，則 minVal 不需要更新；
  • 否則表明插入的 val 小于或者等于當(dāng)前的 minVal，則更新 minVal = val。
• pop()：我們需要根據(jù) diff 來更新彈出棧頂元素后的 minVal，具體地：
  • 先彈出棧頂元素 diff，并 pop；
  • 如果 diff > 0，說明我們當(dāng)時插入的 val 大于當(dāng)時的 minVal，則 minVal 是不需要更新的；
  • 否則說明當(dāng)時插入的 val 小于或者等于 minVal，當(dāng)時的 minVal 是插入的 val，需要將 minVal 還原回去，即當(dāng)時插入 val 更新 minVal 的過程如下，還原回去得到 minVal = minVal + diff。

$$diff=val?minVal;minVal=val;$$

• top()：如果 diff < 0，表示 minVal 就是最小棧的棧頂元素，否則 minVal + diff 才是最小棧的棧頂元素。
• getMin()：直接返回 minVal 即可。

實現(xiàn)代碼

class MinStack {
private:
    stack<long long> stk;
    long long minVal, diff;
public:
    MinStack() {
    }
    
    void push(int val) {
        if (stk.empty()) {
            stk.push(0);
            minVal = val;
        }
        else {
            diff = val - minVal;
            stk.push(diff);
            minVal = diff > 0 ? minVal : val;
        }
    }
    
    void pop() {
        diff = stk.top();
        stk.pop();
        if (diff < 0) {
            minVal = minVal - diff;
        }
    }
    
    int top() {
        return stk.top() < 0 ? minVal : minVal + stk.top();
    }
    
    int getMin() {
        return minVal;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

復(fù)雜度分析

時間復(fù)雜度：$O(1)$。

空間復(fù)雜度：$O(1)$。

其他語言

python3

以下只給出方法三的 python3 代碼，該方法比較巧妙，值得好好研究。

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min_value = x
        else:
            diff = x-self.min_value
            self.stack.append(diff)
            self.min_value = self.min_value if diff > 0 else x

    def pop(self) -> None:
        if self.stack:
            diff = self.stack.pop()
            if diff < 0:
                self.min_value = self.min_value - diff

    def top(self) -> int:
        return self.min_value if self.stack[-1] < 0 else self.stack[-1] + self.min_value

    def getMin(self) -> int:
        return self.min_value if self.stack else -1

寫在最后

如果文章內(nèi)容有任何錯誤或者您對文章有任何疑問，歡迎私信博主或者在評論區(qū)指出 ??????。

如果大家有更優(yōu)的時間、空間復(fù)雜度方法，歡迎評論區(qū)交流。

最后，感謝您的閱讀，如果感到有所收獲的話可以給博主點一個 ?? 哦。文章來源地址http://www.zghlxwxcb.cn/news/detail-718874.html

到了這里，關(guān)于【面試經(jīng)典150 | 棧】最小棧的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！