設(shè)計一個支持 push 饼记，pop 香伴，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧具则。
-
push(x)—— 將元素 x 推入棧中即纲。 -
pop()—— 刪除棧頂?shù)脑亍?/li> -
top()—— 獲取棧頂元素。 -
getMin()—— 檢索棧中的最小元素博肋。
示例:
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
輸出：
[null,null,null,null,-3,null,0,-2]
解釋：
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ù)時間內(nèi)獲得棧中的最小值低斋，因此不能在 getMin() 的時候再去計算最小值，最好應(yīng)該在 push 或者 pop 的時候就已經(jīng)計算好了當(dāng)前棧中的最小值匪凡。
前排的眾多題解中膊畴，基本都講了「輔助棧」的概念病游，這是一種常見的思路唇跨，但是有沒有更容易懂的方法呢？
可以用一個棧，這個棧同時保存的是每個數(shù)字 x 進棧的時候的值 與 插入該值后的棧內(nèi)最小值买猖。即每次新元素 x 入棧的時候保存一個元組：（當(dāng)前值 x改橘，棧內(nèi)最小值）。
這個元組是一個整體政勃，同時進棧和出棧唧龄。即棧頂同時有值和棧內(nèi)最小值，top()函數(shù)是獲取棧頂?shù)漠?dāng)前值奸远，即棧頂元組的第一個值既棺； getMin() 函數(shù)是獲取棧內(nèi)最小值，即棧頂元組的第二個值懒叛；pop() 函數(shù)時刪除棧頂?shù)脑M丸冕。
每次新元素入棧時，要求新的棧內(nèi)最小值：比較當(dāng)前新插入元素 x 和 當(dāng)前棧內(nèi)最小值（即棧頂元組的第二個值）的大小薛窥。
新元素入棧：當(dāng)棧為空胖烛，保存元組 (x, x)；當(dāng)棧不空诅迷，保存元組 (x, min(此前棧內(nèi)最小值佩番， x)))
出棧：刪除棧頂?shù)脑M。
class MinStack {
Node node;
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
if(node == null) {
node = new Node(x,x);
}
else {
Node next = new Node(x,Math.min(node.min,x));
next.prev = node;
node = next;
}
}
public void pop() {
node = node.prev;
}
public int top() {
return node.val;
}
public int getMin() {
return node.min;
}
private class Node {
int val;
int min;
Node prev;
public Node(int val,int min){
this.val = val;
this.min = min;
}
}
}
