一、題目
定義棧的數(shù)據(jù)結(jié)構(gòu)铲球，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min椭赋、push 及 pop 的時間復雜度都是 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ù)不超過
20000次
三、解題思路
3.1> 維護不完整的有序棧
根據(jù)題目描述拟烫，我們需要定義一個棧結(jié)構(gòu)stack该编，來支持實現(xiàn)MinStack類的push()、pop()和top()方法硕淑。
但是對于min()方法來說课竣，它是用來返回當前堆棧中最小元素的，那么我們可以再創(chuàng)建一個棧結(jié)構(gòu)stackOrder置媳，用來保存一個“不完整”的有序棧于樟，其存儲規(guī)則如下所示：
- 當新元素
x小于/等于 stackOrder的棧頂元素時，元素x可以保存到stackOrder的棧頂拇囊。- 當新元素
x大于 stackOrder的棧頂元素時迂曲，元素x不執(zhí)行入棧操作。
那么通過如上規(guī)則寥袭，stackOrder中的元素就是從棧頂開始路捧，自上而下逐一變大的，而棧頂就是當前最小的元素传黄。
我們講完了入棧規(guī)則杰扫，那么出棧呢？針對于stackOrder來說膘掰，出棧規(guī)則如下所示：
- 當stack的
棧頂元素等于 stackOrder的棧頂元素時章姓，stack和stackOrder的棧頂元素都出棧。- 當stack的
棧頂元素不等于 stackOrder的棧頂元素時，只有stack的棧頂元素出棧啤覆。
好了苍日，基本解題思路描述完畢了，下面我們舉例窗声，分別入棧-2相恃、0和-3，然后再執(zhí)行3次出棧操作笨觅，再來看一下stack和stackOrder是如何處理的拦耐。具體邏輯如下所示：
3.2> 利用元素記錄“入棧那一刻”的最小值
那么除了上面的解題思路外，我們其實也可以創(chuàng)建一個Node節(jié)點见剩，里面具有如下3個屬性：
- 【int value】當前元素的值杀糯；
- 【int min】當前所有入棧元素中，最小的值苍苞；
- 【Node pre】前一個入棧元素節(jié)點固翰；
那么，針對MinStack類的push()羹呵、pop()和top()方法骂际，我們就可以通過構(gòu)建一個Node鏈表來實現(xiàn)底層邏輯。而針對min()方法來說冈欢，因為每個Node節(jié)點都保存了它入棧之前所有入棧元素中歉铝，最小的值min，所以直接返回當前節(jié)點的min值就可以了凑耻。此處就不畫圖了太示，具體邏輯可以看下面4.2的源碼實現(xiàn)部分。
四香浩、代碼實現(xiàn)
4.1> 維護不完整的有序棧
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)容就這些了：
寫作不易类缤，筆者幾個小時甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的 點贊 & 分享 弃衍。
更多技術(shù)干貨呀非，歡迎大家關(guān)注公眾號“爪哇繆斯” ~ \(o)/ ~ 「干貨分享，每天更新」
