(LeetCode 面試經典 150 題 ) 155. 最小棧（棧）

題目：155. 最小棧

思路：棧，時間復雜度0(n)。

在插入棧元素val時，同時加入一個字段，維護插入當前元素val時的最小值即可。

C++版本：

class MinStack {
public:stack<pair<int,int>> st;MinStack() {// 哨兵st.push({0,INT_MAX});}void push(int val) {st.push({val,min(getMin(),val)});}void pop() {st.pop();}int top() {return st.top().first;}int getMin() {return st.top().second;}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

JAVA版本：

class MinStack {private final Deque<int[]> st=new ArrayDeque<>();public MinStack() {st.push(new int[]{0,Integer.MAX_VALUE});}public void push(int val) {st.push(new int[]{val,Math.min(getMin(),val)});}public void pop() {st.pop();}public int top() {return st.peek()[0];}public int getMin() {return st.peek()[1];}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

GO版本：

type PII struct {x inty int
}type MinStack struct {st []PII 
}func Constructor() MinStack {return MinStack{[]PII{{0,math.MaxInt}}}
}func (this *MinStack) Push(val int)  {this.st=append(this.st,PII{val,min(this.GetMin(),val)})
}func (this *MinStack) Pop()  {this.st=this.st[:len(this.st)-1]
}func (this *MinStack) Top() int {return this.st[len(this.st)-1].x
}func (this *MinStack) GetMin() int {return this.st[len(this.st)-1].y
}/*** Your MinStack object will be instantiated and called as such:* obj := Constructor();* obj.Push(val);* obj.Pop();* param_3 := obj.Top();* param_4 := obj.GetMin();*/