設計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。
push(x) —— 將元素 x 推入棧中。
pop() —— 刪除棧頂?shù)脑亍?br>
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.
輔助棧
復雜度分析
- 時間復雜度：對于題目中的所有操作，時間復雜度均為 O(1)。因為棧的插入、刪除與讀取操作都是 O(1)，我們定義的每個操作最多調用棧操作兩次。
- 空間復雜度：O(n)，其中 n 為總操作數(shù)。最壞情況下，我們會連續(xù)插入 n 個元素，此時兩個棧占用的空間為 O(n)。
設定兩個數(shù)組，一個是作為棧，一個是記錄最小當前最小值的輔助棧數(shù)組
數(shù)據(jù)棧和輔助棧的數(shù)據(jù)要同步添加，出棧也是要同步出，這樣才能保證數(shù)據(jù)一 一對應
push(-2) push(0) push(-3) pop() top()
-3 -3
0 -2 0 -2 0 -2 0 -2
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2
stack minStack stack minStack stack minStack stack minStack stack minStack
type MinStack struct {
stack []int
minStack []int
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{
stack : []int{},
minArr : []int{math.MaxInt64},//記錄最小棧
}
}
func (this *MinStack) Push(x int) {
this.stack = append(this.stack,x) //將元素添加入棧內(nèi)
min := this.minArr[len(this.minArr) - 1] //獲取最小棧中最頂層的最小值
this.minArr = append(this.minArr,Min(min,x))//比較后，將最小值入棧
}
func (this *MinStack) Pop() {
//出棧操作，兩邊都需要出棧，保證兩邊數(shù)據(jù)同步一一對應
this.stack = this.stack[:len(this.stack)-1]
this.minArr = this.minArr[:len(this.minArr)-1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
return this.minArr[len(this.minArr)-1]
}
func Min(a,b int) int{
if a > b {
return b
}
return a
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/
