leetcode力扣 155最小栈 go实现

记录一下leetcode刷题，大牛请绕道

思路

这个题的核心点还是在于用常数时间内检索到最小元素的栈，也就是用空间换时间。这样的话我们设计一个辅助栈，当栈为空的时候，第一次push的话，主栈和辅助栈都同时push传入的值；如果栈不为空，那么就先从辅助栈获取栈顶的值，然后将插入的值与栈顶的值进行比较，将数值小的那个值push进入辅助栈，这样最后调用GetMin()的话就是从辅助栈的栈顶拿值，这个值一定是最小值了。

代码

type MinStack struct {
	stack []int //主栈
	min_stack []int //最小元素辅助栈
}

func Constructor() MinStack {
	return MinStack{
		stack: []int{},
		min_stack: []int{},
	}
}


// 将元素 x 推入栈中。
func (this *MinStack) Push(val int)  {
	minstack_len := len(this.min_stack)
	//如果是空栈的话，都直接入栈即可
	if minstack_len == 0 {
		this.stack = append(this.stack,val)
		this.min_stack = append(this.min_stack,val)
	}else {
		/* 取辅助栈的栈顶元素与插入元素进行比较，将插入元素与辅助栈栈顶元素进行比较
		把小的元素push到辅助栈中
		*/
		this.stack = append(this.stack,val)
		min_top := this.min_stack[minstack_len-1]
		//fmt.Println("min_top",min_top)
		if val > min_top {
			this.min_stack = append(this.min_stack, min_top)
		} else {
			this.min_stack = append(this.min_stack, val)
		}
	}
}


func (this *MinStack) Pop()  {
	stack_len := len(this.stack)
	minstack_len := len(this.min_stack)
	this.stack = this.stack[:stack_len -1]

	this.min_stack = this.min_stack[:minstack_len-1]
}


func (this *MinStack) Top() int {
	stack_len := len(this.stack)
	return this.stack[stack_len -1]
}


func (this *MinStack) GetMin() int {
	minstack_len := len(this.min_stack)
	return  this.min_stack[minstack_len - 1]
}