题目地址(155. 最小栈)
https://leetcode.cn/problems/min-stack/
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
前置知识
公司
思路
- 使用两个栈，一个原来的栈，一个最小辅助栈
- 切片，是左闭右开区间，右边索引不包括在里面
- 初始化时，要注意逗号，另外，最大值是math.MaxInt64
关键点
代码
- 语言支持：Go
Go Code:
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack {
stack: []int{},
// 初始化时，最底下放一个最大值
minStack: []int{math.MaxInt64},
}
}
func (this *MinStack) Push(val int) {
// 压入普通栈
this.stack = append(this.stack, val)
// 最小栈，要比较一下
if val < this.minStack[len(this.minStack) - 1] {
this.minStack = append(this.minStack, val)
} else {
this.minStack = append(this.minStack, this.minStack[len(this.minStack) - 1])
}
}
func (this *MinStack) Pop() {
this.stack = this.stack[:len(this.stack) - 1]
this.minStack = this.minStack[:len(this.minStack) - 1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack) - 1]
}
func (this *MinStack) GetMin() int {
return this.minStack[len(this.minStack) - 1]
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/
复杂度分析
令 n 为数组长度。
- 时间复杂度：
- 空间复杂度：
