未分類

Min Stack

Design, Go, LeetCode, Stack

Min Stack

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.

For Example:

1
2
3
4
5
6
7
8
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.
提示 解題應用
Stack LinkedList

Default:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
type MinStack struct {
    
}
/** initialize your data structure here. */
func Constructor() MinStack {
    
}
func (this *MinStack) Push(x int)  {
    
}
func (this *MinStack) Pop()  {
    
}
func (this *MinStack) Top() int {
    
}
func (this *MinStack) GetMin() int {
    
}
/**
 * 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();
 */

解答思路:

如果前面需要用上stack的部分都是自己實作的話，那麼應該可以很輕易的完成，畢竟只是從頭來接個LinkedList的方式而已，或是用Array來實作，懂得基本概念的話應該很容易。

程式碼解說:

如果是像我一樣用LinkedList來實作的話，就需要有節點的實作，所以就先建立一個節點的架構，包含了該節點要儲存的值與下一個節點的位置，因為stack不會有節點往回走的情況，只有新增與刪除才會造成位置移動

1
2
3
4
type Node struct {
	Val  int
	Next *Node
}

因為題目要的話初始化一個stack，雖然用LinkedList來實作的話大部分的東西是放在節點，不過還是需要有一個地方自始自終都儲放stack的第一個節點的位置，以方便在做新增與刪除時有個依循，而建構的function就直接回傳空的MinStack物件

1
2
3
4
5
6
type MinStack struct {
	Header *Node
}
func Constructor() MinStack {
	return MinStack{}
}

因為stack插入值都是從頭開始放入，所以不需要考量到前一個節點的位置，所以只要將目前頭節點的位置接在新節點位置的後頭即可，也就是在初始化節點的時候連同要新增的值與頭節點的位置塞入就完成了，只是要記得這是頭節點的位置已經是新節點的位置了，所以要把stack的header指向新節點

1
2
3
4
func (this *MinStack) Push(x int) {
	newNode := &Node{x, this.Header}
	this.Header = newNode
}

Pop故名思義就是要將第一個節點給彈出，不過這邊我只要將頭節點的位置指向下一個即可，你也可以再後頭多加一行釋放彈出節點的記憶體空間，換句話說就是砍掉該節點

1
2
3
func (this *MinStack) Pop() {
	this.Header = this.Header.Next
}

Top就直接回傳頭節點所儲存的值即可

1
2
3
func (this *MinStack) Top() int {
	return this.Header.Val
}

最後要找最小值，因為不曉得stack中間會經過多少次的push與pop，當然也可以每次push與pop都確認一次，不過這邊我還是用一個迴圈將整個stack給遍歷一次以找出最小值，你可以設一個很大的數字或是像我一樣放入一個32位元int的極大值來初始化，方便後續比對尋找最小值的節點

1
2
3
4
5
6
7
8
9
10
11
func (this *MinStack) GetMin() int {
	travel := this.Header
	minVal := math.MaxInt32
	for travel != nil {
		if travel.Val < minVal {
			minVal = travel.Val
		}
		travel = travel.Next
	}
	return minVal
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
type Node struct {
	Val  int
	Next *Node
}
type MinStack struct {
	Header *Node
}
func Constructor() MinStack {
	return MinStack{}
}
func (this *MinStack) Push(x int) {
	newNode := &Node{x, this.Header}
	this.Header = newNode
}
func (this *MinStack) Pop() {
	this.Header = this.Header.Next
}
func (this *MinStack) Top() int {
	return this.Header.Val
}
func (this *MinStack) GetMin() int {
	travel := this.Header
	minVal := math.MaxInt32
	for travel != nil {
		if travel.Val < minVal {
			minVal = travel.Val
		}
		travel = travel.Next
	}
	return minVal
}

總結:

Stack的基本概念是資料從頭來插入，而舊的資料就往後移動，取出資料也是從頭先拿，這時舊的資料則往前移動，總之就是先進後出的概念，也因為操作都是在開頭，所以像是用LinkedList實作時就不需要有個節點在頭的前面來確保操作一致。

分享到