最小栈题解

题目

题目解析

我们先来简单看一下他让我们实现的几个方法的作用：

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

题目需要我们实现一个栈，并且能够检索到最小元素的栈

想要做出这道题，我们首先需要知道：栈是一个先进后出的数据类型，也就是说，如果我们一个元素a入栈时，栈里面如果还有其他的元素，那么无论后面这个栈进行了什么操作，只要这个a还在栈中，那么他下层的元素也就一定还在栈中。利用这个思路，我们可以在结构体中定义两个栈，一个栈为主栈，另一个栈用来存储每次入栈的最小值：当一个元素入栈时，首先判断这个元素是不是第一个元素，如果是，那么我们将这个元素入栈，并且加入第二个存储最小栈的栈中；如果这个元素不是第一个元素，那么判断这个元素是否比第二个栈中栈顶元素小，如果比他小的话，将其插入第二个栈的栈顶；如果大于这个栈顶，那么这个元素不可能为最小栈，那么我们将第二个栈的栈顶元素重复插入第二个栈中，删除操作：我们将两个栈的栈顶同时删除，这样我们可以保证两个栈中的元素个数一样，并且保证第二个栈的栈顶元素一定就是当前栈的最小值，我们在获取最小栈时直接将第二个栈的栈顶返回。

代码实现

type MinStack struct {
	nums    []int
	minNums []int
}

/** initialize your data structure here. */
func Constructor() MinStack {
	return MinStack{
		nums:    []int{}, //栈
		minNums: []int{}, //记录入栈时每个元素对应的最小值
	}
}

func (this *MinStack) Push(x int) {
	//元素入栈
	this.nums = append(this.nums, x)
	//如果是第一个元素或者新入的元素x比之前的最小值还小
	if len(this.minNums) == 0 || x < this.minNums[len(this.minNums)-1] {
		this.minNums = append(this.minNums, x)
	} else { //新入的元素x不比之前的最小值小
		this.minNums = append(this.minNums, this.minNums[len(this.minNums)-1])
	}
}

func (this *MinStack) Pop() {
	if len(this.nums) < 1 {
		return
	}
	this.nums = this.nums[0 : len(this.nums)-1]
	this.minNums = this.minNums[0 : len(this.minNums)-1]
}

func (this *MinStack) Top() int {
	if len(this.nums) < 1 {
		return -1
	}
	return this.nums[len(this.nums)-1]
}

func (this *MinStack) GetMin() int {
	if len(this.nums) < 1 {
		return -1
	}
	return this.minNums[len(this.minNums)-1]
}

总结

这道题考查了对栈特性的了解，使用栈的先进后出特性能够很巧妙的解决这个问题