查看題目詳情可點(diǎn)擊此處。

題目

設(shè)計(jì)一個(gè)支持 push，pop，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。

• push(x) -- 將元素 x 推入棧中。
• pop() -- 刪除棧頂?shù)脑亍?/li>
• top() -- 獲取棧頂元素。
• getMin() -- 檢索棧中的最小元素。

示例:

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

解題思路

需要實(shí)現(xiàn)的棧操作中，其他操作屬于常規(guī)的棧操作，沒(méi)有特別之處，解題的重點(diǎn)在于如何實(shí)現(xiàn)常數(shù)時(shí)間類(lèi)檢索到最小值，實(shí)現(xiàn)此操作需要額外的存儲(chǔ)空間對(duì)最小值進(jìn)行存儲(chǔ)，最初肯定會(huì)考慮到用一個(gè) int 變量存儲(chǔ)最小值，每次 push 操作的時(shí)候比較元素替換最小值，檢索最小值的時(shí)候?qū)⒋?int 變量返回即可。

這樣的方法初看沒(méi)有問(wèn)題，但當(dāng)進(jìn)出棧操作時(shí)，如果棧頂元素就是當(dāng)前的最小值，出棧后就需要在棧內(nèi)元素中再搜索一遍最小值并保存起來(lái)，無(wú)疑會(huì)增加出棧操作的時(shí)間復(fù)雜度。

利用空間換時(shí)間的思想，可以創(chuàng)建另一個(gè)棧，當(dāng)數(shù)據(jù)入棧時(shí)會(huì)存入數(shù)據(jù)棧，同時(shí)也會(huì)把此元素對(duì)應(yīng)的最小值存儲(chǔ)在最小值棧中，類(lèi)似備忘錄模式，記錄下每個(gè)元素的最小值狀態(tài)。

代碼實(shí)現(xiàn)

class MinStack {

    /** initialize your data structure here. */
    private Stack<Integer> intStack;
    private Stack<Integer> minStack;
    private int min;

    public MinStack() {
        intStack = new Stack<>();
        minStack = new Stack<>();
        min = Integer.MIN_VALUE;
    }

    public void push(int x) {
        intStack.push(x);

        if(minStack.empty()) {
            minStack.push(x);
        } else {
            min = Math.min(minStack.peek(), x);
            minStack.push(min);
        }
    }

    public void pop() {
        intStack.pop();
        minStack.pop();
    }

    public int top() {
        return intStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}