155. 最小栈
文章目录
- [155. 最小栈](https://leetcode.cn/problems/min-stack/)
-
- ==思路==
-
- – 辅助栈
- – 不使用辅助栈，使用变量记录最小值
- 结语
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int value) 将元素 value 推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["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)时间复杂度取出最小值，那我们就有三个办法，一个是维护最小栈，一个是给栈排序，一个是记录最小值，这里我们直接pass给栈排序，因为这违背了栈的定义，且栈排序之后在取出顶部元素的时候会直接出错，辅助栈就是最小栈，栈顶维护最小值，方便直接取出，记录最小值是下一个方法
-
时间复杂O(1)，空间复杂度O(n)（我们就不把返回长度的库函数当做O(n)，这里也可以使用一个变量记录长度，当入栈就++，出栈就–，这样时间复杂度就是O(1)了）
-
代码演示
- type MinStack struct {
//记录所有元素的栈
val []int
//维护单调栈
min []int
}func Constructor() MinStack {
//初始化，分配内存
minStack := MinStack{
val : []int{},
min : []int{},
}
return minStack
}func (this *MinStack) Push(value int) {
//如果push进来元素，我们应该直接入val栈
this.val = append(this.val, value)
//如果入栈的元素比最小值还要小，那我们要入最小栈，否则就不入栈
//另外一种情况是如果最小栈里面为空，那我们直接入栈
if len(this.min) == 0 || value <= this.GetMin() {
this.min = append(this.min, value)
}
}func (this *MinStack) Pop() {
//删除val栈顶的元素的时候，我们要考虑栈顶元素是不是等于最小栈栈顶的元素，因为如果等于最小栈的栈顶元素，我们此时要弹出两个栈顶的元素
if this.val[len(this.val)–1] == this.min[len(this.min)–1] {
this.min = this.min[:len(this.min)–1]
}
this.val = this.val[:len(this.val)–1]
}func (this *MinStack) Top() int {
//直接返回val栈顶元素
return this.val[len(this.val)–1]
}func (this *MinStack) GetMin() int {
//返回最小栈的栈顶元素
return this.min[len(this.min)–1]
}
– 不使用辅助栈，使用变量记录最小值
-
我们可以使用min 变量记录最小值，把每一次要入栈的元素与当前的元素做差，如果差小于0，那我们就更换，否则就不更换，如果弹出栈顶的元素，我们判断当前栈顶元素与最小值的差，如果等于0，那我们就更新最小值，这里需要O(n)时间复杂度，依次遍历，如果是返回最小值，我们直接把该变量的值返回即可
-
时间复杂度O(n)，空间复杂度O(1)
-
代码演示
- type MinStack struct {
//入栈每一个元素
valStack []int
//维护最小值
min int
}func Constructor() MinStack {
return MinStack{
valStack : []int{},
//初始化为int32的最大值
min : math.MaxInt32,
}
}func (this *MinStack) Push(value int) {
//比较，如果新入栈的元素更小，更换值
if value < this.GetMin() {
this.min = value
}this.valStack = append(this.valStack, value)
}func (this *MinStack) Pop() {
//如果弹出的元素就等于最小值，我们需要更新最小值，时间复杂度为O(n)
if this.Top() == this.min {
minTemp := math.MaxInt32
//不遍历最后一位，给长度-1
for i := 0; i < this.L()–1; i++ {
if this.valStack[i] < minTemp {
minTemp = this.valStack[i]
}
}
//更新
this.min = minTemp
}
//弹出栈顶元素
this.valStack = this.valStack[:this.L()–1]
}func (this *MinStack) Top() int {
return this.valStack[len(this.valStack)–1]
}func (this *MinStack) GetMin() int {
return this.min
}func (this *MinStack) L() int {
return len(this.valStack)
}/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(value);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/
结语
本文是 《算法题目解析系列》 的第 [27] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。
