問題：
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Example:MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
大意：
設(shè)計一個棧纪挎，支持push期贫、pop、top以及在固定時間內(nèi)檢索最小元素异袄。
- push(x) -- 將元素x放入棧中通砍。
- pop() -- 從棧的頂端移除元素。
- top() -- 獲取棧頂元素烤蜕。
- getMin() -- 檢索棧中的最小元素
例子:MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
思路：
這道題對于棧的操作本身都不難封孙，并不是要用隊列或者別的數(shù)據(jù)結(jié)構(gòu)來模擬一個棧，直接就允許用棧來做讽营。真正難的在于檢索最小元素敛瓷，并且還要再固定時間內(nèi)。
要在入棧以及出棧的同時不停地計算最小元素斑匪，首先棧本身是不支持的呐籽，如果用數(shù)組之類的來記錄，那么每次有新元素進(jìn)來都需要排個序蚀瘸，非常耗時狡蝶。
因此，這種方法巧妙地在每次入棧贮勃、出棧時進(jìn)行簡單的加減操作贪惹，達(dá)到可以直接獲取最小元素的結(jié)果。在入棧時寂嘉，入的不是實(shí)際的元素值奏瞬，而是與當(dāng)前記錄的最小值的差值，如果新入的更小泉孩，就將其設(shè)為最小值硼端，此時就保證了隨時可以獲取最小值。出棧時寓搬，要修改最小值珍昨。獲取棧頂元素時，因為棧中記錄的并不是原始值，所以要與記錄的最小值進(jìn)行操作來還原镣典。
由于題目在submit時會用超過int范圍的大數(shù)來測試兔毙，所以只能用long來操作。
他山之石（Java）：
public class MinStack {
Stack<Long> stack;
long min;
/** initialize your data structure here. */
public MinStack() {
stack=new Stack<Long>();
}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(0L);
min = x;
} else {
stack.push(x - min);
if (x < min) min = x;
}
}
public void pop() {
if (stack.isEmpty()) return;
long pop = stack.pop();
if (pop < 0) min = min - pop;
}
public int top() {
long top = stack.peek();
if (top < 0) return (int)min;
else return (int)(min + top);
}
public int getMin() {
return (int)min;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
合集：https://github.com/Cloudox/LeetCode-Record
