一、題目

定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時(shí)間復(fù)雜度都是 O(1) 。

二、示例

2.1> 示例:

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

提示：

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

三、解題思路

3.1> 維護(hù)不完整的有序棧

根據(jù)題目描述，我們需要定義一個(gè)棧結(jié)構(gòu)stack，來(lái)支持實(shí)現(xiàn)MinStack類的push()、pop()和top()方法。

但是對(duì)于min()方法來(lái)說(shuō)，它是用來(lái)返回當(dāng)前堆棧中最小元素的，那么我們可以再創(chuàng)建一個(gè)棧結(jié)構(gòu)stackOrder，用來(lái)保存一個(gè)“不完整”的有序棧，其存儲(chǔ)規(guī)則如下所示：

• 當(dāng)新元素x 小于/等于 stackOrder的棧頂元素時(shí)，元素x可以保存到stackOrder的棧頂。
• 當(dāng)新元素x 大于 stackOrder的棧頂元素時(shí)，元素x不執(zhí)行入棧操作。

那么通過(guò)如上規(guī)則，stackOrder中的元素就是從棧頂開(kāi)始，自上而下逐一變大的，而棧頂就是當(dāng)前最小的元素。

我們講完了入棧規(guī)則，那么出棧呢？針對(duì)于stackOrder來(lái)說(shuō)，出棧規(guī)則如下所示：

• 當(dāng)stack的棧頂元素 等于 stackOrder的棧頂元素時(shí)，stack和stackOrder的棧頂元素都出棧。
• 當(dāng)stack的棧頂元素 不等于 stackOrder的棧頂元素 時(shí)，只有stack的棧頂元素出棧。

好了，基本解題思路描述完畢了，下面我們舉例，分別入棧-2、0和-3，然后再執(zhí)行3次出棧操作，再來(lái)看一下stack和stackOrder是如何處理的。具體邏輯如下所示：

3.2> 利用元素記錄“入棧那一刻”的最小值

那么除了上面的解題思路外，我們其實(shí)也可以創(chuàng)建一個(gè)Node節(jié)點(diǎn)，里面具有如下3個(gè)屬性：

• 【int value】當(dāng)前元素的值；
• 【int min】當(dāng)前所有入棧元素中，最小的值；
• 【Node pre】前一個(gè)入棧元素節(jié)點(diǎn)；

那么，針對(duì)MinStack類的push()、pop()和top()方法，我們就可以通過(guò)構(gòu)建一個(gè)Node鏈表來(lái)實(shí)現(xiàn)底層邏輯。而針對(duì)min()方法來(lái)說(shuō)，因?yàn)槊總€(gè)Node節(jié)點(diǎn)都保存了它入棧之前所有入棧元素中，最小的值min，所以直接返回當(dāng)前節(jié)點(diǎn)的min值就可以了。此處就不畫圖了，具體邏輯可以看下面4.2的源碼實(shí)現(xiàn)部分。

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

4.1> 維護(hù)不完整的有序棧

class MinStack {
    private Deque<Integer> stack, stackOrder;
    public MinStack() {
        stack = new ArrayDeque<>();
        stackOrder = new ArrayDeque<>();
    }
    public void push(int x) {
        stack.addLast(x);
        if (stackOrder.isEmpty() || min() >= x) stackOrder.addLast(x);
    }
    public void pop() {
        int x = stack.removeLast();
        if (min() == x) stackOrder.removeLast();
    }
    public int top() {return stack.getLast();}
    public int min() {return stackOrder.getLast();}
}

4.2> 利用元素記錄“入棧那一刻”的最小值

class MinStack {
    public Node top;
    public MinStack() {}
    public void push(int x) {
        top = new Node(x, top == null ? x : Math.min(x, top.min), top);
    }
    public void pop() {top = top.pre;}
    public int top() {return top.value;}
    public int min() {return top.min;}
}
class Node {
    public int value, min;
    public Node pre;
    public Node(int value, int min, Node pre) {
        this.value = value;
        this.min = min;
        this.pre = pre;
    }
}

今天的文章內(nèi)容就這些了：

寫作不易，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來(lái)您幾秒鐘的 點(diǎn)贊 & 分享 。

更多技術(shù)干貨，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(^o)/ ~ 「干貨分享，每天更新」