我在网上看到一道算法题,题目如下:
定义一个包含min
函数的栈,通过min
我们可以得到栈中最小的数,并且pop
、push
和min
的时间复杂度都为O(1)。
我知道pop
和push
的复杂度是O(1),但是我不知道如何使得min
的复杂度也为O(1)。如果我定义一个变量来记住每次push
时的最小值,但是当pop
时,最小值可能会改变,所以我需要找到第二小的数,这意味着pop
的复杂度不能为O(1)。
那么我该如何定义这个栈来满足要求呢?
我在网上看到一道算法题,题目如下:
定义一个包含min
函数的栈,通过min
我们可以得到栈中最小的数,并且pop
、push
和min
的时间复杂度都为O(1)。
我知道pop
和push
的复杂度是O(1),但是我不知道如何使得min
的复杂度也为O(1)。如果我定义一个变量来记住每次push
时的最小值,但是当pop
时,最小值可能会改变,所以我需要找到第二小的数,这意味着pop
的复杂度不能为O(1)。
那么我该如何定义这个栈来满足要求呢?
只需使用另一个栈来存储最小值。当你向普通栈中推送一个值时,在min栈中也推送一个值。当你从普通栈中弹出一个值时,也要从min栈中弹出一个值。将要推送到min栈中的值将是当前min栈顶部和新值中的最小值。
以下是Python示例实现:
class MinStack:
def __init__(self):
self.values = []
self.minimums = []
def push(self,value):
self.values.append(value)
if len(self.minimums)==0:
self.minimums.append(value)
else:
self.minimums.append(min(self.min(),value))
def pop(self):
self.minimums.pop()
return self.values.pop()
def min(self):
return self.minimums[-1]
push
函数是O(1),它是一个常数时间,不随stack
中的数字变化而变化。 - hiwaystruct node
{
int data;
node *next;
int min_so_far;
}
min_so_far
保存了包括它本身在内的所有节点的最小值。
因此,当您插入一个新节点时,只需将当前节点的值与现有顶部节点的min_so_far值进行比较,并设置新节点的min_so_far=min(顶部节点的min_so_far,当前节点的值)
弹出时,您无需执行任何操作。
这很容易实现。
*next
。 - hiway在编程中,当push
一个值时,您可以将最小值保存在堆栈变量中。如果push
的值大于下一个push
值,则将min
变量设置为当前push
值。
例如:
class _stack {
int minValue;
struct stackBucket{
int data;
}
....
void push(int lastData){
//push to the stack
if(lastData < minValue) {
minValue = lastData;
}
}
int min(){ return minValue;}
};
min()
函数与堆栈中的元素数量无关。 - Aniket IngeO(n)
的。对于n个元素,您将执行n次此操作。因此是O(n)
。 - Srikar AppalarajuminValue
是栈的顶部元素,则在弹出时,minValue
将无效。 - hiway