设计一个支持 push,pop,top 和 min 操作的栈,min 为获取栈中的最小元素,要求 push、pop、top 和 min 都是 O(1) 时间复杂度。
实现 MinStack 类:
medium。
★★★★☆
出题公司:腾讯、虾皮。
因为要在常数时间内检索到最小元素,我们可以利用空间换时间的思想,使用辅助栈来记录最小元素。
按照上面的思路,我们只需要设计一个数据结构,使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈,与元素栈同步插入与删除,用于存储与每个元素对应的最小值。
当一个元素要入栈时,我们取当前辅助栈的栈顶存储的最小值,与当前元素比较得出最小值,将这个最小值插入辅助栈中;
当一个元素要出栈时,我们把辅助栈的栈顶元素也一并弹出;
在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶。
复杂度分析:
时间复杂度:因为栈的插入、删除与读取操作都是 O(1),我们定义的每个操作最多调用栈操作两次。
空间复杂度:如果栈中的元素为 n,那么辅助栈空间也为 n,所以空间复杂度为 O(n)。
#include <limits.h>
#include <stack>
class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX);
}
void push(int x) {
x_stack.push(x);
min_stack.push(std::min(min_stack.top(), x));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int min() {
return min_stack.top();
}
};
import "math"
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{
stack: []int{},
minStack: []int{math.MaxInt64},
}
}
func (this *MinStack) Push(x int) {
this.stack = append(this.stack, x)
top := this.minStack[len(this.minStack)-1]
this.minStack = append(this.minStack, min(x, top))
}
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) Min() int {
return this.minStack[len(this.minStack)-1]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int min() {
return minStack.peek();
}
}