30.md

包含min函数的栈

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有： push(value):将value压入栈中 pop():弹出栈顶元素 top():获取栈顶元素 min():获取栈中最小元素

进阶：栈的各个操作的时间复杂度是 O(1)，空间复杂度是 O(n)

示例

输入：["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

返回值：-1,2,1,-1

思路

• 整一个辅助栈【可以理解为最小元素的历史快照】
• 新元素小于辅助栈栈顶push新元素
• 新元素大于等于辅助栈栈顶push辅助栈栈顶
• pop同时操作两个栈
• top操作就返回normal的栈顶
• min操作就返回minval的栈顶

实现

package main

var stack []int
var history []int

// 包含min函数的栈
func main() {
	Push(-1)
	Push(2)
	Min()
	Top()
	Pop()
	Push(1)
	Top()
	Min()
}

func Push(node int) {
	stack = append(stack, node)
	if len(history) == 0 {
		history = append(history, node)
	} else {
		top := history[len(history)-1]
		if node < top {
			history = append(history, node)
		} else {
			history = append(history, top)
		}
	}
}

func Pop() {
	stack = stack[:len(stack)-1]
	history = history[:len(history)-1]
}

func Top() int {
	return stack[len(stack)-1]
}

func Min() int {
	return history[len(history)-1]
}